LeetCode746使用最小花费爬楼梯（动态规划）

原理

1. 问题分析与状态定义
   • 题目给定一个表示每阶楼梯花费的数组 cost，每次可以选择爬 1 阶或 2 阶楼梯，目标是求出到达楼梯顶部的最小花费。定义状态 dp[i] 表示到达第 i 阶楼梯所花费的最小成本。
   • 由于可以从第 i - 1 阶跨 1 步或者从第 i - 2 阶跨 2 步到达第 i 阶，所以到达第 i 阶的最小花费取决于到达前一阶（i - 1 阶）的最小花费加上第 i - 1 阶本身的花费 cost[i - 1]，以及到达前两阶（i - 2 阶）的最小花费加上第 i - 2 阶本身的花费 cost[i - 2] 这两种情况中的较小值，由此得出状态转移方程。
2. 边界条件确定
   • 对于第 0 阶楼梯，初始认为不需要花费就能到达，所以 dp[0] = 0。
   • 对于第 1 阶楼梯，同样可以直接从起始位置到达，花费也为 0，即 dp[1] = 0。这两个边界条件为后续动态规划计算提供了基础起始值。

步骤

1. 动态规划数组初始化
   • 创建一个大小为 cost.size() + 1 的 vector 数组 dp，用于存储到达每阶楼梯的最小花费。并将 dp[0] 初始化为 0，dp[1] 也初始化为 0，这是前面提到的边界条件。
2. 动态规划计算
   • 通过循环从第 2 阶楼梯开始计算，循环变量 i 从 2 递增到 cost.size()。对于每一个 i，根据状态转移方程 dp[i] = min((dp[i - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2]))，比较从第 i - 1阶上来（花费为 dp[i - 1] + cost[i - 1]）和从第 i - 2 阶上来（花费为 dp[i - 2] + cost[i - 2]）这两种情况的花费，取较小值作为到达第 i 阶楼梯的最小花费，并存储到 dp[i] 中。
3. 结果返回
   • 循环结束后，dp[cost.size()] 中存储的就是到达楼梯顶部（也就是最后一阶楼梯）的最小花费，将其返回作为最终答案。

图示法表示步骤（以 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 为例）

1. 初始化
   • 创建 dp 数组，大小为 11（因为 cost 数组长度为 10，dp 数组要包含到最后一阶楼梯对应的位置，所以是 cost.size() + 1），并设置 dp[0] = 0，dp[1] = 0。此时 dp 数组状态为：[0, 0, _, _, _, _, _, _, _, _, _]（“_” 表示待计算的值）。
2. 计算 dp[2]
   • 根据状态转移方程 dp[2] = min((dp[2 - 1] + cost[2 - 1]), (dp[2 - 2] + cost[2 - 2])) = min((dp[1] + cost[1]), (dp[0] + cost[0])) = min((0 + 100), (0 + 1)) = 1。此时 dp 数组状态变为：[0, 0, 1, _, _, _, _, _, _, _, _]。
3. 计算 dp[3]
   • dp[3] = min((dp[3 - 1] + cost[3 - 1]), (dp[3 - 2] + cost[3 - 2])) = min((dp[2] + cost[2]), (dp[1] + cost[1])) = min((1 + 1), (0 + 100)) = 2。dp 数组变为：[0, 0, 1, 2, _, _, _, _, _, _, _]。
4. 依次计算后续值
   • 继续按照上述方式计算 dp[4]、dp[5] 等，例如：
   • dp[4] = min((dp[4 - 1] + cost[4 - 1]), (dp[4 - 2] + cost[4 - 2])) = min((dp[3] + cost[3]), (dp[2] + cost[2])) = min((2 + 1), (1 + 1)) = 2。
   • dp[5] = min((dp[5 - 1] + cost[5 - 1]), (dp[5 - 2] + cost[5 - 2])) = min((dp[4] + cost[4]), (dp[3] + cost[3])) = min((2 + 1), (2 + 1)) = 3。
   • 不断重复这个过程，直到计算出 dp[10]。
5. 最终结果
   • 最后 dp[10] 中存储的就是到达楼梯顶部的最小花费，也就是本题的答案。

代码程序以及代码关键行注释

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size() + 1);  // 创建动态规划数组dp，大小为cost数组长度 + 1，用于存储到达每阶楼梯的最小花费
        dp[0] = 0;  // 初始化dp[0]，表示到达第0阶楼梯花费为0
        dp[1] = 0;  // 初始化dp[1]，表示到达第1阶楼梯花费为0

        for (int i = 2; i <= cost.size(); i++) {  // 从第2阶楼梯开始循环计算到达每阶楼梯的最小花费
            dp[i] = min((dp[i - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2]));  // 根据状态转移方程，比较两种到达方式的花费，取最小值作为到达第i阶楼梯的最小花费
        }

        return dp[cost.size()];  // 返回到达楼梯顶部（最后一阶楼梯）的最小花费
    }
};

完整代码程序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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 - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2]));
        }
        return dp[cost.size()];
    }
};

int main() {
    vector<int> cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};  // 这里可以修改cost数组的值来测试不同情况
    Solution solution;
    int result = solution.minCostClimbingStairs(cost);
    cout << "到达楼梯顶部的最小花费为: " << result << endl;
    return 0;
}

时间复杂度分析

1. 计算过程
   • 代码中有一个循环，循环变量 i 从 2 递增到 cost.size()，循环执行的次数为 cost.size() - 1 次，每次循环内部执行的操作主要是根据状态转移方程计算 dp[i] 的值，这个计算过程包含两次加法和一次 min 函数调用（用于比较两个值取较小值），这些操作的时间复杂度都是常数级别。
2. 时间复杂度
   • 所以整个算法的时间复杂度为 ，其中 n 是 cost 数组的长度，即楼梯的阶数，时间复杂度与输入的楼梯阶数呈线性关系。
3. 影响因素及优化方向
   • 时间复杂度主要受楼梯阶数（也就是 cost 数组长度）的影响，阶数越多，计算所需时间越长。可以考虑对状态转移方程进行一些等价变换或者利用特定的数据结构来优化计算过程，但对于本题的常规动态规划解法，其时间复杂度已经相对比较高效，在实际应用中，如果输入规模非常大且对性能有极高要求时，可以进一步探索更高级的优化策略，不过这往往会增加代码的复杂度。

总结

1. 算法特点及适用场景
   • 该算法通过动态规划的思路，清晰地定义了状态和状态转移方程，有效地解决了在爬楼梯过程中求最小花费的问题。代码实现较为简洁直观，易于理解和维护。适用于具有类似最优子结构特性的问题，也就是一个问题的最优解可以由其子问题的最优解推导出来的场景，比如一些资源分配、路径选择等问题，只要能合理分析出状态和转移关系，都可以尝试运用动态规划来求解。
2. 注意事项及可能遇到的问题
   • 在使用动态规划解决此类问题时，关键在于准确地定义状态和推导状态转移方程，任何一处出现错误都可能导致最终结果不正确。同时，要注意边界条件的设置，边界条件设置不当会使整个动态规划计算失去正确的起始基础，进而影响后续所有的计算结果。另外，虽然动态规划能有效解决这类问题，但对于大规模数据，可能需要关注时间和空间复杂度，适时考虑优化策略，避免出现性能瓶颈。