线性动态规划-最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。 – 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。
示例 2：
输入：cost = [1,10,1,1,1,10,1,1,10,1]
输出：6
解释：你将从下标为 0 的台阶开始。 – 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 – 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 – 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 – 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 – 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 – 支付 1 ，向上爬一个台阶，到达楼梯顶部。 总花费为 6 。

代码实现：

 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
34
35
36
37
38
39
40
41
42
43
44
45
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2026-08-12 20:31
 * 最后修改: 2026-08-12 21:53
 * 文件描述: 计算到达楼顶所需的最小台阶费用，时间复杂度 O(n)，空间复杂度 O(n)。
 * 核心算法: dp[i] 表示到达第 i 级台阶的最小费用，状态由前一或前两级转移而来。
****************************************************************/

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int compute(vector<int>& cost) {
    // cost 使用 0 下标；dp 使用 1 下标，便于表示“第 i 级台阶”。
    int n = cost.size();

    // dp[i]：踩到第 i 级台阶所需支付的最小累计费用。
    // dp[0] 是虚拟起点，费用为 0。
    vector<int> dp(n + 1, 0);

    // 踩到第 1 级（下标 0）只能支付 cost[0]。
    dp[1] = cost[0];

    for (int i = 2; i <= n; i++) {
        // 到第 i 级可从前一级或前两级走来，再支付当前台阶 cost[i - 1]。
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i - 1];
    }

    // 楼顶在最后一个台阶之后且不收费，可从最后一级或倒数第二级到达。
    return min(dp[n], dp[n - 1]);
}

int main() {
    int n;
    cin >> n;

    // 输入的第 i 个费用对应下标为 i 的台阶。
    vector<int> cost(n);
    for (int i = 0; i < n; i++) cin >> cost[i];

    cout << compute(cost) << endl;
    return 0;
}

OJ: P4174 , Y3461

Previous Lesson
Back to Lesson
Next Topic