怀来县建设局网站,百度竞价推广登录,徐州最新通知,免费简历模板在线下载理论基础
动态规划与贪心的区别并不是学习动态规划所必须了解的#xff0c;所以并不重要。
想要了解动态规划算法题的特点#xff0c;可以直接做下面三道入门简单题练练手感#xff0c;找找感觉#xff0c;很快就能体会到动态规划的解题思想。
总结成一句话就是#xf…理论基础
动态规划与贪心的区别并不是学习动态规划所必须了解的所以并不重要。
想要了解动态规划算法题的特点可以直接做下面三道入门简单题练练手感找找感觉很快就能体会到动态规划的解题思想。
总结成一句话就是动态规划就是利用已知解求未知解利用之前得到的结果得到下一个结果的过程。
详细的基础理论知识可查阅《代码随想录》— 动态规划 — 理论基础 斐波那契数
题目详细LeetCode.509
动态规划入门题详细的题解可查阅《代码随想录》— 斐波那契数
Java解法动态规划
class Solution {public int fib(int n) {if(n 2){return n;}int[] dp new int[n 1];dp[0] 0;dp[1] 1;for(int i 2; i n 1; i){dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}爬楼梯
题目详细LeetCode.70
动态规划入门题思路和解法跟上一题斐波那契数很相似详细的题解可查阅《代码随想录》— 爬楼梯
Java解法动态规划
class Solution {public int climbStairs(int n) {if(n 3){return n;}int[] dp new int[n 1];dp[1] 1;dp[2] 2;for(int i 3; i n 1; i){dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}使用最小花费爬楼梯
题目详细LeetCode.746
又是一道简单题练手非常过瘾解题思路也十分简单由题可知
爬楼梯可以从下标为0或1的台阶开始爬楼梯每一次花费后可选择向上爬一个或者两个台阶
如果那么根据规律假如我们爬上第三个台阶会有两种情况
第一种从下标为0的台阶开始向上爬两个台阶到达第三个台阶第二种从下标为1的台阶开始向上爬一个台阶到达第三个台阶为了使用最小花费爬楼梯我们爬上第三个台阶的消费应该取两种花费情况中的最小值即cost[3] Math.min(cost[1] cost[3], cost[2] cost[3]);同理我们可以得到后序各个台阶花费情况即本题的递推公式为cost[i] Math.min(cost[i - 1] cost[i], cost[i - 2] cost[i]);
当我们遍历结束后得到了到达各个台阶的最小花费但要注意此时我们到达楼梯顶部的最小花费这一最终返回结果还被没计算出来
cost[cost.length - 1]的值仅表示到达第cost.length - 1个台阶的最小花费而已cost[cost.length - 2]的值仅表示到达第cost.length - 2个台阶的最小花费而已那么当我们到达第cost[cost.length - 1]或 cost[cost.length - 2]个台阶后也可以选择向上爬一个或者两个台阶所以我们最后还需要通过比较cost[cost.length - 1]和cost[cost.length - 2]取两者之间的最小值来作为到达楼梯顶部的最小花费
Java解法动态规划
class Solution {public int minCostClimbingStairs(int[] cost) {for(int i 2; i cost.length; i){cost[i] Math.min(cost[i - 1] cost[i], cost[i - 2] cost[i]);}return Math.min(cost[cost.length - 1], cost[cost.length - 2]);}
}
