代码随想录算法训练营Day-32动态规划01 | 理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

理论基础动规问题常见类型基础问题背包问题打家劫舍股票问题子序列问题动规五部曲DP数组以及下标的含义递推公式DP数组初始化DP数组遍历顺序打印DP数组509. 斐波那契数动规五部曲dp[i]代表第i个斐波那契数;递推公式为dp[i]dp[i-1]dp[i-2];把dp[0]、dp[1]初始化为0、1;从前往后遍历从i2开始到n结束注由于当前状态只与前两个状态有关所以可以把dp数组压缩为仅含两个变量只需不断更新dp[0]、dp[1]即可class Solution { public: int fib(int n) { if(n1) return n; //DP数组以及下标的含义 vectorint dp(2); //DP数组初始化 dp[0]0; dp[1]1; int sum0; //递推公式DP数组遍历顺序 for(int i2;in;i){ sumdp[0]dp[1]; dp[0]dp[1]; dp[1]sum; } return sum; } };70. 爬楼梯动规五部曲dp[i]代表有i1个台阶的话所用步数递推公式为dp[i]dp[i-1]dp[i-2];dp初始化为dp[0]1dp[1]2从前往后遍历从i2开始到n-1结束因为最后求的就是有n个台阶的话有几种路径f(n-1)对应这个含义注本题和斐波那契类似也可以压缩class Solution { public: int climbStairs(int n) { if(n2) return n; //明确dp[i]含义有i1个台阶的话所用步数 vectorint dp(2); //初始化dp需要在想清楚递推公式之后dp[0]1dp[1]2 dp[0]1; dp[1]2; int sum0; //递推公式dp[i]dp[i-1]dp[i-2] //遍历顺序 for(int i2;in;i){ sum dp[0]dp[1]; dp[0]dp[1]; dp[1]sum; } //打印dp return sum; } };746. 使用最小花费爬楼梯动规五部曲dp[i]表示到达第i个台阶花的钱数递推公式为dp[i]min(dp[i-1]cost[i-1], dp[i-2]cost[i-2])两种爬楼方式中选择花钱最少的一种dp初始化为dp[0]0dp[1]0到达第0个或第1个台阶不花钱从前往后遍历从i2开始到cost.size()结束因为最后求的是爬完花的钱不是爬到花的钱class Solution { public: int minCostClimbingStairs(vectorint cost) { if(cost.size()2) return min(cost[0],cost[1]); //明确dp[i]含义到达第i个台阶花的钱数 vectorint dp(cost.size()1); //初始化dp需要在想清楚递推公式之后dp[0]0dp[1]0 dp[0]0; dp[1]0; //递推公式dp[i]min(dp[i-1]cost[i-1], dp[i-2]cost[i-2]) //遍历顺序 for(int i2;icost.size();i){ dp[i]min(dp[i-1]cost[i-1], dp[i-2]cost[i-2]); } //打印dp for (int num : dp) cout num ; return dp[cost.size()]; } };