动态规划.746. 使用最小花费爬楼梯
2026-01-07 17:25:31
达到楼梯顶部的最低花费可以通过动态规划高效解决，其核心思路是利用状态转移方程逐步计算每一步的最小花费，避免重复计算。
问题分析：题目要求从楼梯的第0或第1个台阶开始，每次可选择爬1或2个台阶，到达顶部（即索引n的位置，n为数组长度）的最小总花费。由于每一步的选择依赖于前一步或前两步的状态，动态规划是理想解法。
动态规划定义：设dp[i]表示到达第i个台阶的最小花费（注意：i的范围是0到n，其中dp[n]即为顶部）。初始条件为dp[0] = dp[1] = 0，因为可以从这两个台阶直接开始，无需额外花费。
状态转移方程：对于第i个台阶（i ≥ 2），其最小花费由前一步或前两步的最小花费加上当前步的花费决定：dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
dp[i-1] + cost[i-1]：从第i-1个台阶爬1步到i，需支付cost[i-1]。
dp[i-2] + cost[i-2]：从第i-2个台阶爬2步到i，需支付cost[i-2]。
边界条件：
dp[0] = 0：起始台阶0的花费为0。
dp[1] = 0：起始台阶1的花费为0。
实现步骤：
初始化dp数组，长度为n+1，前两项设为0。
遍历从2到n的每个台阶，根据状态转移方程更新dp[i]。
最终返回dp[n]，即到达顶部的最小花费。
示例验证：
示例1：cost = [10,15,20]
dp[0] = 0, dp[1] = 0
dp[2] = min(dp[1]+10, dp[0]+15) = min(10,15) = 10
dp[3] = min(dp[2]+20, dp[1]+15) = min(30,15) = 15
输出：15（与示例一致）。
示例2：cost = [1,100,1,1,1,100,1,1,100,1]
通过动态规划逐步计算，最终dp[10] = 6（与示例一致）。
优化空间复杂度：动态规划的原始解法使用O(n)空间，但可通过滚动数组优化至O(1)。由于dp[i]仅依赖dp[i-1]和dp[i-2]，可用两个变量prev1和prev2替代数组：
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) prev1, prev2 = 0, 0 for i in range(2, n+1): curr = min(prev1 + cost[i-1], prev2 + cost[i-2]) prev2, prev1 = prev1, curr return prev1对比深度优先搜索（DFS）：
普通DFS：存在大量重复计算，时间复杂度为指数级（O(2^n)），效率极低。
记忆化DFS：通过缓存中间结果（如memo数组）避免重复计算，时间复杂度降至O(n)，但需额外空间存储状态。
动态规划：自底向上计算，无需递归栈，空间效率更高（尤其优化后），且逻辑更直观。
总结：动态规划是解决此类问题的最优方法，通过状态转移方程和边界条件定义，可高效计算出最小花费，时间复杂度为O(n)，空间复杂度可优化至O(1)。
热门标签
