第9章｜动态规划
Unit 02 · LeetCode #746 使用最小花费爬楼梯
费用不是写在格子里就自动发生，
先确定“什么时候付钱”。
本单元沿用 Unit 01 的两个前驱结构，但不再统计走法。你需要区分“站在位置上”和“离开该位置”，把每条路线变成一张候选账单，再从中保留最小累计费用。
已恢复上次学习位置阶段、动画、代码槽位和迁移进度均已恢复。
知识桥梁｜Unit 01 → Unit 02
Unit 01：统计到达方式
dp[i] 是到达位置 i 的方案数量，两个互斥来源直接相加。
相同依赖 → 改变状态值
Unit 02：选择最小账单
dp[i] 是到达位置 i 前已经支付的最小费用，两条带费用的候选路线取最小。
本单元贯穿问题当前状态表示“站在哪里”还是“已经支付了什么”？每一条转移边究竟应当携带哪个台阶的费用？
LeetCode #746 原题题面转述、示例、约束与复杂度目标
题目要求
给定整数数组 cost，其中 cost[i] 表示离开第 i 级台阶前需要支付的费用。支付后可以向上走 1 级或 2 级。你可以从索引 0 或索引 1 开始，返回到达楼顶所需的最小费用。
from typing import List
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
pass
输入与输出
- 输入：每一级台阶的费用数组
cost； - 输出：到达数组之后虚拟楼顶位置的最小累计费用。
约束
2 ≤ cost.length ≤ 1000；0 ≤ cost[i] ≤ 999。
示例
输入：cost = [10,15,20]
输出：15
解释：从索引 1 开始，支付 15 后走两级到楼顶。
输出：15
解释：从索引 1 开始，支付 15 后走两级到楼顶。
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
输出：6
复杂度目标
| 方法 | 时间 | 空间 | 作用 |
|---|---|---|---|
| 暴力递归 | O(2ⁿ) | O(n) | 暴露重复状态 |
| 一维 DP | O(n) | O(n) | 显式保存每个位置 |
| 滚动变量 | O(n) | O(1) | 主提交方法 |
六段认知流程
本环节已完成