3693. 爬楼梯 II

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

考点

  • 线性DP

思路

一、问题概述

给定一个正整数 \(n\)，表示需要从第 \(0\) 级台阶走到第 \(n\) 级台阶。 每次可以选择向前迈 1、2 或 3 级台阶，但不同步数对应不同的代价规则：

  • 迈 1 级：需要支付 \[ \text{costs}[i] + 1 \]

  • 迈 2 级：需要支付 \[ \text{costs}[i+1] + 4 \]

  • 迈 3 级：需要支付 \[ \text{costs}[i+2] + 9 \]

其中 \(i\) 表示当前所处的台阶编号（从 0 开始）。

目标是：求到达第 \(n\) 级台阶的最小总代价。

二、状态定义

定义一维动态规划数组： \[ f[i] = \text{到达第 } i \text{ 级台阶的最小总代价} \] 这是一个典型的最短路径型 DP，每个状态只依赖于更小编号的状态。

三、初始条件

  • 起点位于第 \(0\) 级台阶，不需要任何代价： \[ f[0] = 0 \]

  • 其余状态初始化为一个足够大的值（表示尚不可达）： \[ f[i] = +\infty \quad (i > 0) \]

四、状态转移方程（重点）

假设当前已经处在第 \(i\) 级台阶，且 \(f[i]\) 已经是最优值，则可以进行如下三种转移：

1. 向前迈 1 级

若 \(i + 1 \le n\)，则： \[ f[i+1] = \min\bigl(f[i+1],\ f[i] + \text{costs}[i] + 1\bigr) \]

2. 向前迈 2 级

若 \(i + 2 \le n\)，则： \[ f[i+2] = \min\bigl(f[i+2],\ f[i] + \text{costs}[i+1] + 4\bigr) \]

3. 向前迈 3 级

若 \(i + 3 \le n\)，则： \[ f[i+3] = \min\bigl(f[i+3],\ f[i] + \text{costs}[i+2] + 9\bigr) \]

五、转移顺序与正确性说明

  • 台阶编号是严格递增的，因此可以按照 \[ i = 0 \rightarrow n-1 \] 的顺序进行状态转移。

  • 每个状态只依赖于编号更小的状态，满足 无后效性。

  • 所有可能到达某个台阶的路径都会在转移过程中被枚举到，因此最终的 \(f[n]\) 一定是全局最优解。

六、空间优化思想

观察状态转移可知：

  • \(f[i]\) 只会影响 \[ f[i+1],\ f[i+2],\ f[i+3] \]

  • 不需要保存完整的 DP 数组，只需维护一个长度为 4 的“滑动窗口”。

可以使用滚动变量：

  • cur：当前 \(f[i]\)
  • f1：未来的 \(f[i+1]\)
  • f2：未来的 \(f[i+2]\)
  • f3：未来的 \(f[i+3]\)

每次循环后整体向前平移，从而将空间复杂度从 \(O(n)\) 优化为 \(O(1)\)。

七、时间与空间复杂度

  • 时间复杂度： \[ O(n) \] 每个台阶只进行常数次转移。

  • 空间复杂度：

    • 普通 DP：\(O(n)\)
    • 滚动优化：\(O(1)\)

八、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
30
class Solution {
public:
    static const int maxn = 1e5 + 5;

    int climbStairs(int n, vector<int>& costs) {
        int f[maxn];

        // 初始化为无穷大
        memset(f, 0x3f, sizeof(f));

        // 初始状态
        f[0] = 0;

        for (int i = 0; i < n; ++i) {
            // 走 1 级
            if (i + 1 <= n)
                f[i + 1] = min(f[i + 1], f[i] + costs[i] + 1);

            // 走 2 级
            if (i + 2 <= n)
                f[i + 2] = min(f[i + 2], f[i] + costs[i + 1] + 4);

            // 走 3 级
            if (i + 3 <= n)
                f[i + 3] = min(f[i + 3], f[i] + costs[i + 2] + 9);
        }

        return f[n];
    }
};

版本二：滚动变量优化（\(O(1)\) 空间）

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
30
31
32
33
class Solution {
public:
    static const int maxn = 1e5 + 5;
    static const int inf = INT_MAX >> 1;

    int climbStairs(int n, vector<int>& costs) {
        // cur 表示 f[i]
        int cur = 0;

        // 分别表示 f[i+1], f[i+2], f[i+3]
        int f1 = inf, f2 = inf, f3 = inf;

        for (int i = 0; i < n; ++i) {
            // 从当前状态尝试更新未来状态
            if (i + 1 <= n)
                f1 = min(f1, cur + costs[i] + 1);

            if (i + 2 <= n)
                f2 = min(f2, cur + costs[i + 1] + 4);

            if (i + 3 <= n)
                f3 = min(f3, cur + costs[i + 2] + 9);

            // 状态整体前移
            cur = f1;
            f1 = f2;
            f2 = f3;
            f3 = inf;
        }

        return cur;
    }
};