【代码随想录day32】【C++复健】509. 斐波那契数；70. 爬楼梯；746. 使用最小花费爬楼梯
今天的内容相对比较基础，作为一个二周目的人做这些题相对还是容易的。
不过dp五部曲有些忘了，在这里再记录一下：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
509. 斐波那契数
虽然也是一遍写出来，但这样的定义方法假如是从后往前遍历就不行了。所以最好还是按照解析里的写法，写成vector<int> dp(N + 1);的样子比较好。
class Solution {
public:
int fib(int n) {
vector<int> dp;
dp.push_back(0);
dp.push_back(1);
for(int i=2; i<=n; i++){
dp.push_back(dp[i-1]+dp[i-2]);
}
return dp[n];
}
};70. 爬楼梯
好像做了两道题，又好像做了一道题似的。这次改进了上面一个题的问题。
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n+1);
dp[0] = 1;
dp[1] = 1;
for(int i=2; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};746. 使用最小花费爬楼梯
这个题有一个稍微绕一点的点在于，本题的dp[0]并不是什么都不干的dp[0]，而是迈上序号为0，实则为第一级台阶所需要花费的cost。
在上一题中，我们的dp[0]代表的是什么都不干，但本题实际上是迈了一步的。
为什么会有这一点区别呢？我们可以从题设里面看出来。
70的爬楼梯里面说“需要迈n级台阶”，也就是说实际上我们只要迈到高度为n的台阶就可以停下了。也就是当0代表什么都不干的时候，n正好代表迈了n级台阶。
而本题的爬楼梯，如果我们按照之前的方式来定义，当我到达最后一个位置，也就是dp[cost.size()]这个位置，实际上代表的是到达cost数组最后一个元素所需要的花费，我们还需要往上迈一步，才算按照题设里说的，“达到楼梯顶部”。而我们如果把dp[0]设为迈了1步的情况的话，恰好dp[cost.size()]这个位置才对应的是到达顶部的cost。
理解了这一点之后，想要写出来整体代码就并不复杂了。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n= cost.size();
vector<int> dp(n+1);
dp[0] = 0;
dp[1] = 0;
for(int i=2; i<=n; i++){
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
}
return dp[n];
}
};