746. 使用最小花费爬楼梯 - 力扣（LeetCode）
解法 1：动态规划（O(n) 时间，O(n) 空间）
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n = len(cost)dp = [0] * (n + 1) # 额外多一个 dp[n]for i in range(2, n + 1):dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])return dp[n]✅ 优点：清晰直观，容易理解。
⚠️ 缺点：需要 O(n) 额外空间存储 dp 数组。
解法 2：动态规划 + 空间优化（O(n) 时间，O(1) 空间）
优化思路
- 由于
dp[i]仅依赖dp[i-1]和dp[i-2]，因此可以用 两个变量 代替dp数组，优化空间。 - 设
prev2表示dp[i-2]，prev1表示dp[i-1]，curr表示dp[i]。
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n = len(cost)prev2, prev1 = 0, 0 # 对应 dp[0] 和 dp[1]for i in range(2, n + 1):curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2])prev2, prev1 = prev1, curr # 滚动更新return prev1✅ 优点：O(1) 空间复杂度，适用于大规模输入。
✅ 缺点：相比数组版本，可读性稍差。
解法 3：原地修改（O(n) 时间，O(1) 空间）
思路
直接修改 cost 数组，使 cost[i] 存储到达 i 级台阶的最小花费，最终返回 min(cost[-1], cost[-2])。
class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:n = len(cost)for i in range(2, n):cost[i] += min(cost[i - 1], cost[i - 2])return min(cost[-1], cost[-2])✅ 优点：无需额外变量，直接在原数组上计算，节省空间。
⚠️ 缺点：会修改输入数据，如果 cost 需要保留，不能用此方法。
最佳选择
| 方法 | 时间复杂度 | 空间复杂度 | 适用情况 |
|---|---|---|---|
| DP 数组 | O(n) | O(n) | 适用于小规模输入，代码易理解 |
| DP + 滚动数组 | O(n) | O(1) | 推荐，适合大规模输入 |
| 原地修改 | O(n) | O(1) | 适用于不需要保留 cost 数组 |
🔹 小规模输入（n < 1000），DP 数组版可读性好。
🔹 大规模输入（n > 10^6），推荐 滚动变量版（O(1) 空间）。
🔹 如果可以修改 cost 数组，可以用 原地修改版。