### 题目描述 假设你正在爬楼梯，需要 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 ```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 ```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 ```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]); } ``` **码小课**：在码小课网站上，你可以找到更多关于动态规划、算法优化等内容的详细讲解和练习，帮助你更深入地理解和应用这些算法技巧。