509. 斐波那契数
刚开始学编程的时候就遇到过的题，虽然说现在学的是动态规划，但是我是用递归做出来的。
class Solution {
public:
int fib(int n) {
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
return fib(n-1)+fib(n-2);
}
};
看了动态规划的解法，我就又用动态规划写了一遍。
需要注意的是：初始化sum的时候，大小要写成n+1才可以，因为例如3的话，需要储存0 1 2 3四个数的结果。
class Solution {
public:
int fib(int n) {
if(n<2){
return n;
}
vector<int> sum(n+1);
sum[0] = 0;
sum[1] = 1;
int result = 0;
for(int i=2; i<=n; i++){
sum[i] = sum[i-1] + sum[i-2];
}
return sum[n];
}
};
70. 爬楼梯
自己想复杂了，看了题解才会写！
比如达到第5层，可能的组合只能是从第三阶跨两步上来 或者是第四阶跨一步上来。所以所有的可能就是第三阶的结果和第四阶的结果加起来就是了。之所以不用在之前的基础上加1，是因为我们算的是多少种组合，不是说走了多少步。从第三阶的答案中，就能得到如果走到了第三阶，就只能从这第三阶里所有的组合中走到第五阶，不可能是第三阶，但又有了新的组合。
class Solution {
public:
int climbStairs(int n) {
if(n == 1){
return n;
}
vector<int> dp(n+1);
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
746. 使用最小花费爬楼梯
这道题自己做出来了一半。我想到了应该用min来求上一步和上两步的最小值，但是我没捋清楚什么时候加cost。应该是只有在从上一步要继续往前走的时候，再把那一步的cost加上。
我们之所以创造一个大小为cost.size()+1的dp数组，是因为例如[10,15,20]，我们应该在20之后停下来。因为我们dp设的是到达第i台阶所需要的体力，所以如果算到i=2也就是对应数是20的时候，我们算的是走到这一步需要最少是多少的体力。得算到i=3也就是过了20之后，才是我们真正需要的答案。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size()+1);
dp[0] = 0;
dp[1] = 0;
for(int i=2; i<=cost.size(); i++){
dp[i] = min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]);
}
return dp[cost.size()];
}
};
