斐波那契

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        vector<int> dp(N + 1);//创建一个n+1大小的数组()vector<int> dp(n);表示创建大小为n的数组， vector<vector<int>> dp(row, vector<int>(col));表示创建row行 col列的二维数组
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[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];
    }
};

爬楼梯

关于初始话dp[0]是1还是0的讨论？------------------>题目没有说，你管他干什么？

需要注意的是：题目中说了n是一个正整数，题目根本就没说n有为0的情况。

所以本题其实就不应该讨论dp[0]的初始化！

我相信dp[1] = 1，dp[2] = 2，这个初始化大家应该都没有争议的。

所以我的原则是：不考虑dp[0]如果初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样才符合dp[i]的定义。
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;//注意这里的dp[2]陷阱！！如果n=1；那么这里就是越界
        for (int i = 3; i <= n; i++) { // 注意i是从3开始的
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

优化同上

花费体力的爬楼梯

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {//cost[i]是爬上那个i对应的体力值，而不是从这层离开需要的体力值
        vector<int> dp(cost.size());//dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]到达
        dp[0] = cost[0];//爬到第0层需要花费第0层对应的体力值
        dp[1] = cost[1];
        for (int i = 2; i < cost.size(); i++) {
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        }//题目没说最后一步
        // 所以最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
        return min(dp[cost.size() - 1], dp[cost.size() - 2]);
    }
};