509 斐波那契数

思路：

如果 n 小于等于 1，则直接返回 n，因为斐波那契数列的前两项分别为 0 和 1
定义一个长度为 2 的数组 dp，用于存储斐波那契数列的前两项
初始化 dp[0] 为 0，dp[1] 为 1
使用循环计算 dp 数组中的每一项，从 2 开始到 n
计算 dp 数组中前两项的和，存储在变量 sum 中
更新 dp 数组中的值，dp[0] 被赋值为原来的 dp[1]，dp[1] 被赋值为 sum
循环结束后，返回 dp[1]，即斐波那契数列的第 n 项。

1.动态规划

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

70 爬楼梯

思路：此题和上题一摸一样，甚至代码都很接近，都是dp[i] = dp[i - 1] + dp[i - 2]

1.动态规划

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 1) return n;
        int dp[2];
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 3; i <= n; i++){
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

746 使用最小花费爬楼梯

思路：

定义一个长度为 2 的数组 dp，用于存储到达当前台阶的最小代价
初始化 dp[0] 和 dp[1] 的值都为 0，表示到达前两个台阶的最小代价都为 0
使用循环计算到达每个台阶的最小代价，从第三个台阶开始到达最后一个台阶
计算到达当前台阶的最小代价，根据动态规划的状态转移方程 dpi = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])，其中 i 表示当前台阶的编号，dpi 表示到达当前台阶的最小代价
更新 dp 数组中的值，dp[0] 被赋值为原来的 dp[1]，dp[1] 被赋值为 dpi
循环结束后，返回 dp[1]，即到达最后一个台阶的最小代价。

1.动态规划

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int dp[2];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= cost.size(); i++){
            int dpi = min(dp[1] + cost[i - 1], dp[0] + cost[i - 2]);
            dp[0] = dp[1];
            dp[1] = dpi;
        }
        return dp[1];
    }
};