Medium

题目描述

你正在爬一个有 n + 1 级台阶的楼梯，台阶编号从 0 到 n。

你还有一个长度为 n 的 1 索引整数数组 costs，其中 costs[i] 是第 i 级台阶的成本。

从第 i 级台阶，你只能跳到第 i + 1、i + 2 或 i + 3 级台阶。从第 i 级台阶跳到第 j 级台阶的成本定义为：costs[j] + (j - i)²

你从第 0 级台阶开始，成本为 0。

返回到达第 n 级台阶的最小总成本。

示例 1：

输入：n = 4, costs = [1,2,3,4] 输出：13 解释： 一个最优路径是 0 → 1 → 2 → 4

跳跃成本计算成本
0 → 1costs[1] + (1 - 0)² = 1 + 12
1 → 2costs[2] + (2 - 1)² = 2 + 13
2 → 4costs[4] + (4 - 2)² = 4 + 48

因此，最小总成本是 2 + 3 + 8 = 13

示例 2：

输入：n = 4, costs = [5,1,6,2] 输出：11 解释： 一个最优路径是 0 → 2 → 4

跳跃成本计算成本
0 → 2costs[2] + (2 - 0)² = 1 + 45
2 → 4costs[4] + (4 - 2)² = 2 + 46

因此，最小总成本是 5 + 6 = 11

示例 3：

输入：n = 3, costs = [9,8,3] 输出：12 解释： 最优路径是 0 → 3，总成本 = costs[3] + (3 - 0)² = 3 + 9 = 12

约束条件：

  • 1 <= n == costs.length <= 10⁵
  • 1 <= costs[i] <= 10⁴

解题思路

这是一道典型的动态规划问题。关键是理解状态转移和成本计算。

思路分析：

  1. 状态定义：设 dp[i] 表示到达第 i 级台阶的最小成本
  2. 初始状态：dp[0] = 0，起始位置成本为 0
  3. 状态转移：对于台阶 j，可以从台阶 j-1、j-2 或 j-3 跳过来
    • 从台阶 i 跳到台阶 j 的成本 = costs[j] + (j-i)²
    • dp[j] = min(dp[i] + costs[j] + (j-i)²) 其中 i ∈ {j-1, j-2, j-3}

优化思路：

由于每个位置只依赖前面最多3个位置，我们可以直接用一维 DP 数组。遍历每个位置时，检查所有可能的前驱位置（最多3个），选择成本最小的路径。

时间复杂度：O(n)，每个位置最多检查3个前驱 空间复杂度：O(n)，需要 DP 数组存储每个位置的最小成本

代码实现

class Solution {
public:
    int climbStairs(int n, vector<int>& costs) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        for (int j = 1; j <= n; j++) {
            for (int step = 1; step <= 3; step++) {
                int i = j - step;
                if (i >= 0) {
                    dp[j] = min(dp[j], dp[i] + costs[j - 1] + step * step);
                }
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def climbStairs(self, n: int, costs: List[int]) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for j in range(1, n + 1):
            for step in range(1, 4):
                i = j - step
                if i >= 0:
                    dp[j] = min(dp[j], dp[i] + costs[j - 1] + step * step)
        
        return dp[n]

public class Solution {
    public int ClimbStairs(int n, int[] costs) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = int.MaxValue;
        }
        dp[0] = 0;
        
        for (int j = 1; j <= n; j++) {
            for (int step = 1; step <= 3; step++) {
                int i = j - step;
                if (i >= 0) {
                    dp[j] = Math.Min(dp[j], dp[i] + costs[j - 1] + step * step);
                }
            }
        }
        
        return dp[n];
    }
}

var climbStairs = function(n, costs) {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let j = 1; j <= n; j++) {
        for (let step = 1; step <= 3; step++) {
            const i = j - step;
            if (i >= 0) {
                dp[j] = Math.min(dp[j], dp[i] + costs[j - 1] + step * step);
            }
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n)
空间复杂度O(n)