509. 斐波那契数

class Solution {
public:
    int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int a1 = 0, a2 = 1;
        int a3;
        for (int i = 0; i < n - 1; i ++)
        {
            a3 = a1 + a2;
            a1 = a2;
            a2 = a3;
        }
        return a3;
    }
};

70. 爬楼梯

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int a1 = 1, a2 = 2;
        int a3;
        for (int i = 0; i < n - 2; i ++)
        {
            a3 = a1 + a2;
            a1 = a2;
            a2 = a3;
        }
        return a3;
    }
};

746. 使用最小花费爬楼梯

有一点点的反向思维在里面？每个点只能从idx-1 和 idx-2两个中选一个

class Solution {
public:
    // 从 idx-1 和 idx-2 中选一个
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1);

        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];
    }
};