746. 使用最小花费爬楼梯

发表于 分类于 阅读次数： Waline： 本文字数： 770 阅读时长 ≈ 3 分钟

考点

  • 线性DP

思路

一、问题重述

给定一个长度为 \(n\) 的数组 cost，其中 cost[i] 表示踏上第 \(i\) 个台阶所需要支付的代价。 从台阶 \(0\) 或台阶 \(1\) 开始，每一步可以向上走 1 阶或 2 阶，目标是到达 第 \(n\) 阶（楼顶），并使总花费最小。

注意：到达第 \(n\) 阶本身不需要额外花费。

二、问题建模（状态定义）

这是一个典型的一维动态规划最短路径问题。

状态定义

定义状态： \[ f[i] = \text{到达第 } i \text{ 阶时所需要的最小花费} \] 其中：

  • \(i \in [0, n]\)
  • 第 \(n\) 阶表示楼顶，不对应 cost 中的任何元素

三、初始状态（边界条件）

根据题意：

  • 可以从台阶 \(0\) 或台阶 \(1\) 作为起点，且起点不需要支付任何代价

因此有： \[ f[0] = 0,\quad f[1] = 0 \] 其余状态初始化为一个足够大的值（表示“尚不可达”）。

四、状态转移方程

考虑从第 \(i\) 阶出发的转移（\(0 \le i < n\)）：

  • 若从第 \(i\) 阶走 1 步 到 \(i+1\)，需要支付 cost[i]
  • 若从第 \(i\) 阶走 2 步 到 \(i+2\)，同样需要支付 cost[i]

因此转移方程为： \[ \begin{aligned} f[i+1] &= \min\bigl(f[i+1],\; f[i] + \text{cost}[i]\bigr) \\ f[i+2] &= \min\bigl(f[i+2],\; f[i] + \text{cost}[i]\bigr) \end{aligned} \] 该转移完整覆盖了所有合法路径。

五、计算顺序与答案

  • 状态 \(f[i]\) 只依赖于更小的下标，因此按 \(i = 0 \rightarrow n-1\) 顺序递推即可
  • 最终答案为：

\[ \boxed{f[n]} \]

六、时间与空间复杂度

  • 时间复杂度： \[ O(n) \]

  • 空间复杂度（基础版本）： \[ O(n) \]

由于每个状态只依赖前两个状态，可以进一步进行空间压缩。

七、AC代码

版本一：标准 DP（数组写法，直观清晰）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    // 最大台阶数上限（题目规模 <= 1000）
    static const int maxn = 1e3 + 5;

    int minCostClimbingStairs(vector<int>& cost) {
        int f[maxn];
        int n = cost.size();

        // 将 f 数组初始化为一个很大的值，表示“不可达”
        memset(f, 0x3f, sizeof(f));

        // 起点：可以从 0 或 1 开始，且不花费任何代价
        f[0] = 0;
        f[1] = 0;

        // 动态规划递推
        for (int i = 0; i < n; ++i) {
            // 从 i 走 1 步到 i+1
            f[i + 1] = min(f[i + 1], f[i] + cost[i]);

            // 从 i 走 2 步到 i+2
            f[i + 2] = min(f[i + 2], f[i] + cost[i]);
        }

        // 到达第 n 阶（楼顶）的最小花费
        return f[n];
    }
};

版本二：空间压缩 DP（滚动变量）

该版本基于如下事实： \[ f[i] \text{ 只依赖 } f[i-1], f[i-2] \] 因此可用常数变量滚动维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    static const int inf = INT_MAX >> 1;

    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();

        // f0 表示 f[i]
        // f1 表示 f[i+1]
        // f2 表示 f[i+2]
        int f0 = 0, f1 = 0, f2 = inf;

        for (int i = 0; i < n; ++i) {
            // 从 f0（即 f[i]）转移
            f1 = min(f1, f0 + cost[i]); // 到 i+1
            f2 = min(f2, f0 + cost[i]); // 到 i+2

            // 状态整体前移
            f0 = f1;
            f1 = f2;
            f2 = inf; // 重置 f2，避免污染下一轮
        }

        // f0 最终对应 f[n]
        return f0;
    }
};