理论基础
总结一下就是：
动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
动态规划五部曲
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509. 斐波那契数
1.递归
class Solution {
public int fib(int n) {
if(n == 0 || n == 1)
return n;
return fib(n - 1) + fib(n - 2);
}
}2.dp
先按照动态规划的五部曲
1.确定dp数组以及下标的含义：dp数组表示的就是Fn，其中dp[i] = Fi.
2.确定递归公式：F(n) = F(n - 1) + F(n - 2).
3.dp数组的初始化：dp[0] = 0,dp[1] = 1.
4.确定遍历顺序：2~n.
5.举例推导dp数组：dp[2] = dp[1] + dp[0] = 1.
可以写出下面代码：
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 ;i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}但是对于这道题，其实我们只需要用到最后的dp[n],所以代码可以改为：
class Solution {
public int fib(int n) {
if(n < 2)
return n;
int res = 0;
int first = 0;
int second = 1;
for(int i = 2;i <= n ;i++){
res = first + second;
first = second;
second = res;
}
return res;
}
}70. 爬楼梯
思路：可以跟上面一样用递归，或者dp做，dp分析如下:
1.dp数组表示的是从第一节台阶到第n个台阶的方式数，dp[i]表示的是从1~i有多少种走法。
2.递推公式：dp[i] = dp[i - 1] + dp[i - 2]。
3.dp数组的初始化：dp[1] = 1,dp[2] = 2;
4.遍历顺序：3~n
5.举例推导递推公式：dp[3] = dp[2] + dp[1];
class Solution {
public int climbStairs(int n) {
int[] dp = {0,1,2};
if(n < 3)
return dp[n];
int res = 0;
for(int i = 3; i <= n;i++){
res = dp[1] + dp[2];
dp[1] = dp[2];
dp[2] = res;
}
return res;
}
}746. 使用最小花费爬楼梯
思路：还是使用五部曲进行分析，但是这里特殊的一点就是，最后for循环里我们只算到了cost.length处，还没有到达顶部，可以在最后的时候比较一下，倒数第一步和倒数第二步，哪个更少，取一个min就是result了。
class Solution {
public int minCostClimbingStairs(int[] cost) {
if(cost.length == 2)
return Math.min(cost[0],cost[1]);
int[] dp = new int[2];
dp[0] = cost[0];
dp[1] = cost[1];
int res = 0;
for(int i = 2;i < cost.length;i++){
res = cost[i] + Math.min(dp[0],dp[1]);
dp[0] = dp[1];
dp[1] = res;
}
res = Math.min(res,dp[0]);
return res;
}
}总结：五部曲确实很好用，可以分析得也更透彻(๑•̀ㅂ•́)و✧
标签：契数,爬楼梯,int,res,随想录,cost,数组,return,dp From： https://blog.csdn.net/weixin_46002954/article/details/143814830