公司网站后台登陆百度问一问付费咨询
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509. 斐波那契数
https://leetcode.cn/problems/fibonacci-number/
class Solution {public int fib(int n) {if(n==0) return 0;if(n<3) return 1;int[] dp = new int[n];dp[0]=1;dp[1]=1;for(int i=2;i<n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n-1];}
}
讲解的简化版本。
class Solution {public int fib(int n) {if (n < 2) return n;int a = 0, b = 1, c = 0;for (int i = 1; i < n; i++) {c = a + b;a = b;b = c;}return c;}
}
70. 爬楼梯
https://leetcode.cn/problems/climbing-stairs/
和斐波那契差不多。
class Solution {public int climbStairs(int n) {if(n<4) return n;int[] dp=new int[n];int a=2;int b=3;int c=5;for(int i=3;i<n;i++){c=a+b;a=b;b=c;}return c;}
}
746. 使用最小花费爬楼梯
https://leetcode.cn/problems/min-cost-climbing-stairs/
这个感觉最后一步不花费更好理解
class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp=new int[cost.length];dp[0]=cost[0];dp[1]=cost[1];for(int i=2;i<cost.length;i++){dp[i]=Math.min(dp[i - 1], dp[i - 2]) + cost[i];}return Math.min(dp[cost.length-1],dp[cost.length-2]);}
}