当前位置：首页 > news >正文

day32-动态规划509. 斐波那契数70. 爬楼梯__746. 使用最小花费爬楼梯

news 来源：原创 2025/9/11 19:32:33

动态规划，一直是各种算法竞赛中难度较大的题目。在同学接触到动态规划的题目时，对于简单的动态规划问题，同学们常常轻易通过，而对于复杂的动态规划，却没有一个很好的思路，那么我们究竟有没有一种统一的思考步骤来解决动态规划问题呢？

卡哥总结了动规五部曲：

确定dp数组及其下标的含义
确定递推公式(状态转移方程)
确定dp公式初始值
确定递推方向（遍历方向）
打印dp数组验证

很多同学认为，dp的难，难在不能很好的总结出递推公式(状态转移方程)，但其实这个只是动规里面的一个难点，只需要想清楚了dp数组及其下标的含义，我们在推导递推公式时，也会事半功倍。

此外，为什么要先确定递推公式，再确定初始值呢？这是因为很多时候递归的初始值，常常需要由递推公式来确定要定义哪几项初始值，要由dp数组的下标及其含义来确定具体的值。

最后，如果在做动规时，得出的答案跟预想的不一致，不妨先将每次状态转移后的dp数组打印出来，看看跟自己所想的是否一致。如果一致的话，去检查是否转移方程或者初始化出现问题。如果不一致，去看看哪里的问题可能导致这个不一致。

509. 斐波那契数

这个问题相信很多朋友都做过，这道题是可以用递归很轻易的解决出来的

代码如下:

class Solution {
public:int fib(int N) {if (N < 2) return N;return fib(N - 1) + fib(N - 2);}
};

显然由于递归，时间复杂度是O(2^n)太高了

我们现在来思考动规的做法

确定dp数组及其下标的含义 -》 dp[i]表示到斐波那契数的第i项的值
确定递推公式(状态转移方程) -》由于斐波那契数列的每一项，由前两项的和推出 dp[i] = dp[i-1] +dp[i-2]
初始化递推公式，由于i由i-1和i-2推出，那么i=1和i=2的值，必须初始化 dp[1] = 1 dp[2] = 1
确定遍历顺序 -》后项由前项推出，所以采取从前向后遍历
打印dp数组

代码如下:

class Solution {
public:int fib(int N) {if (N <= 1) return N;vector<int> dp(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];}
};

时间复杂度O(n) 空间复杂度O(n)

由于每一轮只维护两个数值，所以也可以用变量的方式保存，减少空间消耗

代码如下:

class Solution {
public:int fib(int N) {if (N <= 1) return N;int dp[2];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};

时间复杂度O(N) 空间复杂度O(N)

70. 爬楼梯

这道题我们也用递归五部曲分析一下

确定dp数组及其下标的含义 -》 dp[i]表示到达第i阶台阶的方法总数
确定状态转移方程 -》由于每次只能爬一阶或者二阶，那么dp[i] = dp[i-1] + dp[i-2]
确定初始值 -》由于n从1开始，所以dp[0]无意义，dp[1]根据定义应该等于1，dp[2]应该等于2
确定遍历顺序，后项由前项推出，所以从前向后遍历
打印dp数组验证

代码如下:

class Solution {
public:int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;vector<int> dp(2);dp[0] = 1;dp[1] = 2;for(int i=3;i<=n;i++){int tmp = dp[0] + dp[1];dp[0] = dp[1];dp[1] = tmp;}return dp[1];}
};

不难看出这题代码几乎与上题一致，爬楼梯其实就是斐波那契的应用。

时间复杂度O(N) 空间O(N)

746. 使用最小花费爬楼梯

这道题，我们还是用动规五部曲来分析

确定dp数组及其下标的含义

dp[i] 表示到达第i层的最小花费

确定状态转移方程

根据题目所述可知，第i层，只能由i-1 或者 i-2层走一步得到

那么也就是说，如果想要到达dp[i]的花费最小，就是取到达第i-1层的最小花费 + cost[i-1] 和到达第i-

2层的最小花费 + cost[i-2] -> dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).

确定初始值，由于这里i需要由i-1和i-2推出，又n>=1，所以要初始化dp[1] 和 dp[2]

根据题目描述可以选择从第一层或者第二层出发，也就是说到达第一层或者第二层是不需要花费的

所以有dp[1] = 0 dp[2] = 0

确定遍历顺序由前推后所以从前向后遍历
打印dp数组

有了上述分析，我们能够很容易的写出如下代码

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int size = cost.size(); // cost[i]表示在第i层向上跳所需要的花费vector<int> dp(size+2);dp[0] = 0;dp[1] = 0;   // dp[i] 表示到达第i层所需要的最小花费for(int i=2;i<=size;i++){dp[i] = min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]);}return dp[size];}};

相关文章：