使用最小花费爬楼梯（动态规划）
2021-06-23 14:30:53
使用最小花费爬楼梯的动态规划解法如下：
定义dp数组：
dp[i]表示到达第i个台阶所需的最小花费。
数组长度为n+1，其中n是cost数组的长度，因为楼梯顶部对应下标n。
初始化：
dp[0] = 0，dp[1] = 0。因为可以选择从第0或第1个台阶开始，初始花费为0。
递推公式：
对于2 ≤ i ≤ n，dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。
即从i-1台阶上来的花费与从i-2台阶上来的花费中的较小值。
遍历顺序：
从前向后遍历，计算dp[2]到dp[n]的值。
结果：
dp[n]即为到达楼梯顶部的最小花费。
Python代码实现：
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) dp = [0] * (n + 1) 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)，只需遍历一次cost数组。
- 空间复杂度：O(n)，使用了一个长度为n+1的dp数组。
示例验证：
示例1：
输入：cost = [10, 15, 20]
计算：
dp[2] = min(dp[1] + 15, dp[0] + 10) = min(0 + 15, 0 + 10) = 10
dp[3] = min(dp[2] + 20, dp[1] + 15) = min(10 + 20, 0 + 15) = 15
输出：15
示例2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
计算过程：
dp[2] = min(dp[1] + 100, dp[0] + 1) = min(0 + 100, 0 + 1) = 1
dp[3] = min(dp[2] + 1, dp[1] + 100) = min(1 + 1, 0 + 100) = 2
dp[4] = min(dp[3] + 1, dp[2] + 1) = min(2 + 1, 1 + 1) = 2
dp[5] = min(dp[4] + 1, dp[3] + 100) = min(2 + 1, 2 + 100) = 3
dp[6] = min(dp[5] + 100, dp[4] + 1) = min(3 + 100, 2 + 1) = 3
dp[7] = min(dp[6] + 1, dp[5] + 1) = min(3 + 1, 3 + 1) = 4
dp[8] = min(dp[7] + 100, dp[6] + 1) = min(4 + 100, 3 + 1) = 4
dp[9] = min(dp[8] + 1, dp[7] + 1) = min(4 + 1, 4 + 1) = 5
dp[10] = min(dp[9] + 1, dp[8] + 100) = min(5 + 1, 4 + 100) = 6
输出：6
优化空间复杂度：
- 注意到dp[i]只依赖于dp[i-1]和dp[i-2]，可以用两个变量代替dp数组：class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) a, b = 0, 0 for i in range(2, n + 1): c = min(b + cost[i - 1], a + cost[i - 2]) a, b = b, c return b
- 空间复杂度优化后：O(1)。
热门标签
