题解 | 最小花费爬楼梯

解题思路

这是一个动态规划问题：

每一步可以选择跨一步或两步
$dp[i]$ 表示到达第 $i$ 个台阶的最小花费
$dp[i] = min(dp[i-1], dp[i-2]) + cost[i]$
最后需要比较到达最后一个台阶和倒数第二个台阶的花费

代码

c++
java
python

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

int main() {
    int n;
    cin >> n;
    vector<int> cost(n);
    for(int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    
    vector<int> dp(n);
    dp[0] = cost[0];
    dp[1] = cost[1];
    
    for(int i = 2; i < n; i++) {
        dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
    }
    
    cout << min(dp[n-1], dp[n-2]) << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] cost = new int[n];
        for(int i = 0; i < n; i++) {
            cost[i] = sc.nextInt();
        }
        
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        
        for(int i = 2; i < n; i++) {
            dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
        }
        
        System.out.println(Math.min(dp[n-1], dp[n-2]));
        sc.close();
    }
}

n = int(input())
cost = list(map(int, input().split()))

dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]

for i in range(2, n):
    dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

print(min(dp[n-1], dp[n-2]))

算法及复杂度

算法：动态规划
时间复杂度： $\mathcal{O}(n)$ ，其中n为台阶数量
空间复杂度： $\mathcal{O}(n)$ ，可以优化到 $\mathcal{O}(1)$

这道题的关键点：

使用动态规划数组记录到达每个台阶的最小花费
每个位置的最小花费取决于前两个位置的最小值
最终结果是倒数第一个和倒数第二个台阶的最小值
可以通过滚动数组将空间复杂度优化到 $\mathcal{O}(1)$