题目描述

假设你正在爬楼梯，需要 n 步你才能到达楼顶。每次你可以爬 1 或 2 个台阶。爬楼梯的过程中，每一步台阶都对应一个费用（正整数），现在给你一个数组 cost，其中 cost[i] 表示你爬第 i+1 个台阶需要支付的费用。一旦你支付了费用，你就可以爬到相应的台阶上。

你需要找到达到楼顶所需的最少费用，并返回这个费用值。

示例 1:

输入: cost = [10, 15, 20]
输出: 15
解释: 最低成本的方式是：第一步花费 10，第二步花费 5，总费用为 15。

示例 2:

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低成本的方式是：第一步到第六步每步都花费 1，第七步花费 100，第八步到第九步每步都花费 1，总费用为 6。

解题思路

这个问题是一个典型的动态规划问题。我们可以定义一个数组 dp，其中 dp[i] 表示达到第 i 个台阶所需的最少费用。根据题目要求，我们可以推导出状态转移方程：

• dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-1])，对于 i >= 2
• 初始条件为 dp[0] = 0（从地面开始不需要费用），dp[1] = cost[0]（第一步的费用）

代码示例

PHP

function minCostClimbingStairs($cost) {
    $n = count($cost);
    if ($n <= 1) return $cost[0] ?? 0;
    
    $dp = array_fill(0, $n, 0);
    $dp[0] = $cost[0];
    $dp[1] = $cost[1];
    
    for ($i = 2; $i < $n; $i++) {
        $dp[$i] = min($dp[$i-1] + $cost[$i], $dp[$i-2] + $cost[$i]);
    }
    
    // 注意题目要求的是达到楼顶，即 n 步后，但数组是从 0 开始的，所以取 dp[n-1] 和 dp[n-2] 中的较小值
    return min($dp[$n-1], $dp[$n-2]);
}

Python

def minCostClimbingStairs(cost):
    n = len(cost)
    if n <= 1:
        return cost[0] if cost else 0
    
    dp = [0] * n
    dp[0] = cost[0]
    dp[1] = cost[1]
    
    for i in range(2, n):
        dp[i] = min(dp[i-1] + cost[i], dp[i-2] + cost[i])
    
    return min(dp[-1], dp[-2])

JavaScript

function minCostClimbingStairs(cost) {
    const n = cost.length;
    if (n <= 1) return n === 0 ? 0 : cost[0];
    
    const dp = new Array(n).fill(0);
    dp[0] = cost[0];
    dp[1] = cost[1];
    
    for (let i = 2; i < n; i++) {
        dp[i] = Math.min(dp[i-1] + cost[i], dp[i-2] + cost[i]);
    }
    
    return Math.min(dp[n-1], dp[n-2]);
}

码小课：在码小课网站上，你可以找到更多关于动态规划、算法优化等内容的详细讲解和练习，帮助你更深入地理解和应用这些算法技巧。