当前位置：首页 > article >正文

一步步讲解：如何通过动态规划解决「爬楼梯最低花费」问题

article 2024/10/25 18:40:00

引言

在面对算法问题时，初学者常常会感到迷茫，不知道从何下手。尤其是像「爬楼梯最低花费」这样的动态规划问题，虽然看起来简单，但如果没有掌握合适的思维框架，往往难以快速找到解题的突破口。动态规划的核心思想是将问题分解为若干个子问题，通过递推的方式找到最优解，而理解这一点是解题的关键。

在这篇博客中，我将带你逐步构建出解决「爬楼梯最低花费」问题的完整动态规划思路。我们会从如何分析问题、构建状态到编写代码，全面展示解题的全过程，并通过优化后的代码，提升算法的效率。希望通过这一讲解，能够帮助你更好地理解动态规划的思维方式，让这类问题变得不再困难。

问题描述

给定一个整数数组 cost，其中 cost[i] 表示从第 i 个台阶向上爬需要支付的费用。每次你可以选择向上爬一个或两个台阶，你可以从第0层或第1层开始，目标是计算爬到楼梯顶端的最低花费。

举例来说：

示例 1：
```
输入: cost = [10, 15, 20]
输出: 15
```
从第 1 层开始，支付 15 到达楼梯顶部，总花费为 15。
示例 2：
```
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
```
从第 0 层开始，支付 1 后一步一步跳到顶部，总花费为 6。

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

动态规划解题思路

我们可以将这个问题抽象为一个最优子结构问题，即：

要到达第 i 个台阶，我们有两种选择：从第 i-1 个台阶或者从第 i-2 个台阶跳上来，选择这两者中花费较小的路径加上当前台阶的花费 cost[i]。

因此，这里我们使用动态规划的思想来解决这个问题。动态规划的核心在于分解问题：当前的最优解是依赖于前面状态的最优解的。

1. 定义状态

我们可以定义一个数组 dp，其中 dp[i] 表示到达第 i 个台阶所需要的最低花费。我们的目标是找到 dp 数组的最优解。

首先我们明确以下几点：

可以从第 0 层或第 1 层开始，因此 dp[0] = cost[0]，dp[1] = cost[1]。
从第 2 层开始，我们需要从前面的两个台阶 i-1 或 i-2 跳上来，因此状态转移方程是：

$\min(dp[i-1], dp[i-2]) + cost[i]$

这意味着到达第 i 个台阶，我们可以选择从 i-1 或 i-2 来，根据这两者中哪一个代价更小，再加上当前台阶的花费。

2. 初始条件

我们从第 0 层或第 1 层开始爬楼梯，所以 dp[0] 和 dp[1] 是已知的，分别等于 cost[0] 和 cost[1]。

3. 最终解

当我们到达楼梯的最后时，楼梯的顶部可以从倒数第二层或最后一层上去。因此，最终的最小花费就是：

$\text{result} = \min(dp[n-1], dp[n-2])$

即：到达最后一个台阶或者倒数第二个台阶的最小花费。

动态规划代码实现

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

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n);
    
    // 初始化第0层和第1层的最小花费
    dp[0] = cost[0];
    dp[1] = cost[1];

    // 通过状态转移方程更新dp数组
    for (int i = 2; i < n; ++i) {
        dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
    }

    // 返回到达楼梯顶部的最小花费
    return min(dp[n-1], dp[n-2]);
}

int main() {
    vector<int> cost1 = {10, 15, 20};
    vector<int> cost2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};

    cout << "最低花费（示例1）: " << minCostClimbingStairs(cost1) << endl;
    cout << "最低花费（示例2）: " << minCostClimbingStairs(cost2) << endl;

    return 0;
}

代码讲解

我们首先定义了一个 dp 数组，存储到达每个台阶的最小花费。
初始阶段，直接把 dp[0] 和 dp[1] 初始化为 cost[0] 和 cost[1]，因为这是最初的起点。
然后从第2层台阶开始，依次根据状态转移方程更新 dp 数组的值。
最后，我们只需要返回 dp[n-1] 和 dp[n-2] 的最小值，因为我们可以从这两层中的任意一层到达楼梯的顶部。

示例分析

示例 1:

输入：cost = [10, 15, 20]

dp[0] = 10
dp[1] = 15
计算 dp[2] = min(dp[1], dp[0]) + cost[2] = min(15, 10) + 20 = 30

结果为 min(dp[1], dp[2]) = min(15, 30) = 15，输出为 15。

示例 2:

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

dp[0] = 1
dp[1] = 100
计算：
- dp[2] = min(dp[1], dp[0]) + cost[2] = min(100, 1) + 1 = 2
- dp[3] = min(dp[2], dp[1]) + cost[3] = min(2, 100) + 1 = 3
- dp[4] = min(dp[3], dp[2]) + cost[4] = min(3, 2) + 1 = 3
- 继续类似地计算到最后。

结果为 min(dp[9], dp[8]) = min(6, 104) = 6，输出为 6。

优化思路：减少空间复杂度

在上面的解法中，我们用了 dp 数组保存每一个台阶的最小花费，但是我们其实只需要保留前两个台阶的最小花费，因此可以将空间复杂度从 O(n) 降低到 O(1)。

优化后的代码如下：

int minCostClimbingStairsOptimized(vector<int>& cost) {
    int n = cost.size();
    int prev1 = cost[1], prev2 = cost[0];

    for (int i = 2; i < n; ++i) {
        int curr = min(prev1, prev2) + cost[i];
        prev2 = prev1;
        prev1 = curr;
    }

    return min(prev1, prev2);
}