代码随想录算法训练营Day38|动态规划理论基础、2.斐波那契数、3.爬楼梯、4.使用最小花费爬楼梯

动态规划理论基础

代码随想录 (programmercarl.com)

动态规划（Dynamic Programming，简称DP）是一种算法设计技术，它通过将复杂问题分解为更小的子问题来解决优化问题。动态规划通常用于解决那些具有重叠子问题和最优子结构特性的问题。（可以理解为一种递推）

重叠子问题：

        在递归算法中，相同的子问题会被多次计算。动态规划通过存储这些子问题的解来避免计算。这个存储通常使用一个表格（数组）来实现，称为备忘录或DP表。

最优子结构：

        一个问题的最优解包含其子问题的最优解。这意味着可以通过组合子问题的最优解来构造原问题的最优解。

动态规划的通常步骤：

1. 定义状态：确定DP数组的含义，即dp[i]通常代表什么意义，比如在斐波那契数列问题中，dp[i]代表第i个斐波那契数。
2. 状态转移方法：确定状态之间如何转移，即如何从一个或多个已知状态的值计算出下一个状态的值，如斐波那契数中 F[i] = F[i-1] + F[i-2]。
3. 初始化：确定DP数组的初始值，这些通常关乎问题的边界条件。如斐波那契数中F[0] = 0,F[1] = 1。
4. 计算顺序：确定DP数组的计算顺序，通常需要按照逻辑顺序从小到大计算。如斐波那契数列需要一次从2开始向后计算得到想要的值。
5. 返回结果：根据DP数组的最终值来确定原问题的解。如返回你需要的斐波那契数。

斐波那契数

509. 斐波那契数 - 力扣（LeetCode）

递推顺序为 F(n) = F(n-1)+F(n-2)

F(0) = 0, F(1) = 1

class Solution {
public:
    int fib(int n) {
       // 如果 n 小于或等于 1，直接返回 n
       // 这是因为斐波那契数列的前两个数是定义好的：F(0) = 0, F(1) = 1
       if(n<=1) return n;
       // 创建一个动态数组 dp，大小为 n+1，用于存储斐波那契数列
       vector<int>dp(n+1);
       // 初始化 dp 数组的前两个数，即 F(0) 和 F(1)
       dp[0] = 0;
       dp[1] = 1;
       // 从 2 开始循环到 n，计算 dp 数组的其余值
       for(int i = 2; i <= n; i++){
            // 根据斐波那契数列的定义，每个数是前两个数的和
            dp[i] = dp[i-1]+ dp[i-2];
       }
       // 返回 dp 数组的最后一个值，即斐波那契数列的第 n 个数
       return dp[n];
    }
};

算法的时间复杂度为O(n)，空间复杂度同样为O(n)，需要维护一个斐波那契数数组。

爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

斐波那契数的一个变体，开始没想到，想到之后只能感慨代码随想录的题目顺序还是很用心的。

假设爬到第i-1层有x种方案，爬到第i-2层有y种方案，那么爬到第i层有x+y种方案(第i-1层再向上爬一层达到i，第i-2层向上爬2层到达i层)。由此，就能看出这个问题是上述斐波那契数的变体。递推关系为dp[i] = dp[i-1] + dp[i-2]，从前往后遍历，dp[0] = 0,dp[1] = 1，爬到1层只有一种方案，dp[2] =2，爬到2层有2种可能 1 1 和 2。具体代码如下，我考虑从3开始计算，最后返回dp[n]。

class Solution {
public:
    // 定义一个名为 climbStairs 的函数，用于计算爬到第 n 阶楼梯的方法数
    int climbStairs(int n) {
        // 如果 n 小于或等于 2，直接返回 n
        // 这是因为当楼梯阶数不超过 2 时，方法数与楼梯阶数相同
        if(n<=2) return n;
        // 创建一个动态数组 dp，大小为 n+1，用于存储到达每一阶楼梯的方法数
        vector<int>dp(n+1);
        // 初始化 dp 数组的前三个数，即到达第 0、1、2 阶的方法数
        // 到达第 0 阶的方法数为 0，因为还没有开始爬,这里也可以认为是1，能减少一点代码量    
        // 这样dp[2]不用赋值
        dp[0] = 0;
        // 到达第 1 阶的方法数为 1，只能爬 1 阶
        dp[1] = 1;
        // 到达第 2 阶的方法数为 2，可以一次爬 2 阶或者分两次各爬 1 阶
        dp[2] = 2;
        // 从 3 开始循环到 n，计算 dp 数组的其余值
        for(int i = 3; i <= n; i++){
            // 根据问题的性质，到达第 i 阶的方法数是到达第 i-1 阶和第 i-2 阶的方法数之和
            // 这是因为每次你可以选择爬 1 阶或 2 阶，所以到达第 i 阶的方法可以从第 i-1 阶爬上来，或者从第 i-2 阶爬上来
            dp[i] = dp[i-1] + dp[i-2];
        }
        // 返回 dp 数组的最后一个值，即到达第 n 阶的方法数
        return dp[n];
    }
};

算法的时间复杂度为O(n)，空间复杂度同样为O(n)，需要维护一个斐波那契数数组。

使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

这里同样是上述问题的变种，但需要考虑的是，这里不是找方案，而是计算损失，所以动态规划数组dp[i]代表的是到达n前的最小花费，到达第i层需要分别计算到达第i-1层和到达第i-2层的损失，然后选择较小的值作为dp[i]的值。由于在到达最终的n层前，每次到达一个i都需要起跳，所以需要添加损失，dp[i]为min(dp[i-1]+cost[i],dp[i-2]+cost[i])，而最后抵达n时，不再需要起跳，只需要考虑dp[n-1]和dp[n-2]的较小值，就是爬楼梯所需的最小花费。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // 获取楼梯的阶数，即成本数组的大小
        int n = cost.size();
        // 创建一个动态数组 dp，大小为 n，用于存储到达每一阶楼梯的最小成本
        vector<int>dp(n);
        // 初始化 dp 数组的前两个数，即到达第 0、1 阶的最小成本
        // 到达第 0 阶的成本就是 cost[0]
        dp[0] = cost[0];
        // 到达第 1 阶的成本就是 cost[1]
        dp[1] = cost[1];
        // 从第 2 阶开始循环到第 n-1 阶，计算 dp 数组的其余值
        for(int i = 2; i < n; i++){
            // 到达第 i 阶的最小成本是到达第 i-1 阶和第 i-2 阶的最小成本加上当前阶梯的成本中的较小值
            // 这是因为每次你可以选择从第 i-1 阶爬上来或者从第 i-2 阶爬上来
            dp[i] = min(dp[i-1] + cost[i], dp[i-2] + cost[i]);
        }
        // 最后，到达楼顶的最小成本是到达倒数第一阶和倒数第二阶的最小成本中的较小值
        // 因为你可以从倒数第一阶直接到达楼顶，也可以从倒数第二阶直接到达楼顶
        return min(dp[n-2], dp[n-1]);
    }
};

算法的时间复杂度为O(n)，遍历cost数组，并计算得到dp数组，空间复杂度同样为O(n)，需要维护一个dp数组。