代码随想录算法训练营第三十八天| 动态规划，509. 斐波那契数，70. 爬楼梯，746. 使用最小花费爬楼梯

本文主要是介绍代码随想录算法训练营第三十八天| 动态规划，509. 斐波那契数，70. 爬楼梯，746. 使用最小花费爬楼梯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划

题目链接： 509. 斐波那契数

思路

代码

题目链接： 70. 爬楼梯

思路

代码

题目链接： 746. 使用最小花费爬楼梯

思路

代码

总结

动态规划

Dynamic programming，DP问题。某一问题包含很多重叠的子问题，每个状态都由上一个状态推导而来。问题包括：基础问题，背包问题，打家劫舍，股票问题，子序列问题，

步骤：

确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

题目链接：509. 斐波那契数

思路

题目给出了dp五部曲中的所有信息。

代码

class Solution {
public:int fib(int n) {if (n <= 1)return n;vector<int> dp(n + 1); // 定义dp数组，dp[i]就是斐波那契数列第i个的值dp[0] = 0;dp[1] = 1; // 按照斐波那契数列初始化前两个数for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2]; // 递推公式}return dp[n];}
};

题目链接：70. 爬楼梯

思路

1阶有1中方法，2阶有两种方法，3阶则是可以从1阶或者2阶走上来，从1或者2走上来总共3种方法。递推下去，发现与斐波那契数列相同，只是该题的0阶并无含义。对求斐波那契数列的代码进行状态压缩，因为每次求值只跟前两个状态有关，因此只需要三个变量，而不是一个数组。

代码

class Solution {
public:int climbStairs(int n) {if (n <= 2)return n;int dp1 = 1; // 一阶台阶int dp2 = 2; // 二阶台阶int result = 0;for (int i = 3; i <= n; i++) {result = dp1 + dp2; // 递推公式dp1 = dp2;          // 更新dp2 = result;}return result;}
};

题目链接：746. 使用最小花费爬楼梯

思路

使用最小消费爬楼梯

1.dp[i]数组含义为到第i阶台阶所需要花费多少

2.递推公式dp[i] = min(dp[i-1]+cost[i-1], [dp[i-2]+cost[i-2])

3.根据题意和dp数组含义，可知在下标为0或1时不需要花费体力，因此dp[0]=0,dp[1]=0

4.遍历顺序，从前向后

5.如果有bug，打印dp数组debug

代码

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size() + 1); // 到第i阶的所有花费dp[0] = 0;                       // 0或1阶不需要花费dp[1] = 0;for (int i = 2; i <= cost.size(); i++) {// 递推公式，每次取最小花费dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.size()]; // 返回最小花费}
};