python-leetcode-使用最小花费爬楼梯

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) 空间）

优化思路

1. 由于 dp[i] 仅依赖 dp[i-1] 和 dp[i-2]，因此可以用 两个变量 代替 dp 数组，优化空间。
2. 设 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 数组，可以用 原地修改版。