LeetCode 746简单一维动态规划
使用最小花费爬楼梯 图解题解
这道题到底在问什么
每次可爬 1 或 2 阶，踩到某阶要付 cost，求到楼顶最小花费。
- 示例
- cost=[10,15,20] → 15
最优解：一步一步想明白
- 3只贪心踩便宜阶会被后面的选择反噬。
- 4dp[i] 表示到达第 i 阶前的最小花费，从 i-1 或 i-2 转移。
- 5上行是各阶的离开费 cost，下行是 dp(到达该阶的最小花费)。先填 dp[0]=dp[1]=0。
- 6到阶2有两条来路：从阶1走1步(付 cost[1]=15) 或 从阶0跳2步(付 cost[0]=10)。取 min → dp[2]=10。
- 7到顶(阶3)：从阶2走1步(付 20) 得 30，或从阶1跳2步(付 15) 得 15。取 min → dp[3]=15。
- 8关键帧：每个台阶 dp[i] 都从「前一阶 +cost[i−1]」和「前两阶 +cost[i−2]」里取较小的。到顶 dp[3]=15 就是答案。
- 9回溯最省路线：从阶 1 免费起步，花 15 一步跳两阶到顶，总花费 15。注意楼顶本身不付费。
- 12一句话记住：dp[i] 表示到达第 i 阶前的最小花费，从 i-1 或 i-2 转移。
- 21这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=dp 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：以为到达楼顶也要付费
✓ 对：楼顶(第 n 阶)不付费，cost 只到 n−1
dp[n] 就是答案；楼顶没有 cost。
✗ 错：dp[0]/dp[1] 设成 cost 值
✓ 对：都设 0(可从阶 0 或 1 免费起步)
题目允许从下标 0 或 1 出发，起步不花钱。
✗ 错：付费付到「到达」的台阶
✓ 对：从第 i 阶迈出才付 cost[i]
cost[i] 是离开第 i 阶的费用，不是到达它的费用。
完整代码（Python / C++ / Java）
Python
class Solution:
def minCostClimbingStairs(self, cost):
a = b = 0
for i in range(2, len(cost) + 1):
a, b = b, min(b + cost[i - 1], a + cost[i - 2])
return bC++
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int a = 0, b = 0;
for (int i=2;i<=cost.size();i++) {
int cur = min(b + cost[i-1], a + cost[i-2]);
a = b; b = cur;
}
return b;
}
};Java
class Solution {
public int minCostClimbingStairs(int[] cost) {
int a = 0, b = 0;
for (int i=2;i<=cost.length;i++) {
int cur = Math.min(b + cost[i-1], a + cost[i-2]);
a = b; b = cur;
}
return b;
}
}套路模板 · 线性 DP（滚动）
# 爬楼梯最小花费骨架 · 滚动变量
a = b = 0 # dp[0]=dp[1]=0
for i in range(2, len(cost)+1):
a, b = b, min(b + cost[i-1], a + cost[i-2]) # 两条来路取 min
return b # b = dp[n] = 到顶复杂度
时间复杂度
O(n)
扫一遍台阶，每阶 O(1) 转移
空间复杂度
O(1)
dp[i] 只依赖前两项，用两个滚动变量即可
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 使用最小花费爬楼梯 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心状态与转移是什么？+
dp[i]=到达第 i 阶的最小花费；dp[i]=min(dp[i−1]+cost[i−1], dp[i−2]+cost[i−2])；dp[0]=dp[1]=0，答案 dp[n]。
这道题为什么用「一维动态规划」，换最直接的暴力解会差在哪？+
一维动态规划抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。