提示
文章目录
一、斐波那契数
当前数值等于前两个数值相加
class Solution {
public:
int fib(int n) {
//1.确定dp数组及含义
//2.确定递推公式
//3.dp数组如何初始化
//4.遍历顺序
//5.举例推导递推公式
if (n <= 1) return n;
vector<int>f(n+1);
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
};
二、爬楼梯
1.确定递推公式,爬i-1层楼梯,有dp[i-1]种方法,爬i-2,有dp[i-2]种方法,可以迈一步或者两步到i阶,所以爬到i层有dp[i-1]+dp[i-2]种方法,不是需要迈几步到i阶,而是有几种方法。从i-2层可以迈两步上来,而到达i-2层有dp[i-2]种方法,同理i-1。
class Solution {
public:
int climbStairs(int n) {
//1.确定dp数组即下标含义
vector<int>dp(n+1);
//2.确定递推公式
if (n <= 2) return n;
//3.dp数组如何初始化
dp[1] = 1;
dp[2] = 2;
//4.遍历顺序
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
三、使用最小花费爬楼梯
思路类似与爬楼梯,可以选择迈一步或者迈两步,在这道题中,需要求最小花费,所以需要从能到i层的方法中找出花费最少的,也就是min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
//1.确定dp数组及下标含义
vector<int>dp(cost.size() + 1);
//2.递推公式
//3.dp数组初始化
dp[0] = 0;
dp[1] = 0;
//4.遍历顺序
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()];
}
};
总结
楼梯和最小花费爬楼梯有点绕,理解了就好很多。
学习时间90min。
学习资料:《代码随想录》。