LeetCode 746：使用最小花费爬楼梯 —— 题解笔记
LeetCode 746：使用最小花费爬楼梯 —— 题解笔记
🔗 题目链接
👉 https://leetcode.cn/problems/min-cost-climbing-stairs/
📖 内容概要
给定一个数组cost，其中cost[i]表示登上第i阶楼梯所需支付的费用。
你可以从第0阶或第1阶开始，支付该台阶的费用后继续向上。
求到达顶层（楼顶）的最小花费。
✅ 动态规划
✅ 一维 DP
✅ 与「爬楼梯」「斐波那契」高度相似
💡 解题思路
一、状态定义（非常关键）
dp[i]=到达第 i 阶楼梯的最小花费⚠️ 注意：
到达第i阶时，还没有支付cost[i]
二、状态转移方程
到达第i阶，只能来自：
- 第
i-1阶，再跨 1 步 - 第
i-2阶，再跨 2 步
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])三、初始条件
dp[0]=0;// 起点dp[1]=0;// 可以从第 1 阶开始四、最终结果
returndp[n];楼顶在第
n阶（数组外）
✅ AC 代码（Java）
classSolution{publicintminCostClimbingStairs(int[]cost){intn=cost.length;int[]dp=newint[n+1];dp[0]=0;dp[1]=0;for(inti=2;i<=n;i++){dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}returndp[n];}}⏱️ 复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间复杂度 | O(n) |
| 空间复杂度 | O(n)（可优化为 O(1)） |
📌 三题横向对比
| 题目 | 本质 | 状态转移 | 初始条件 |
|---|---|---|---|
| 509. 斐波那契数（Fibonacci Number） | 递推 | f(i)=f(i-1)+f(i-2) | f(0)=0, f(1)=1 |
| 70. 爬楼梯（Climbing Stairs） | 方案数 | dp[i]=dp[i-1]+dp[i-2] | dp[0]=1, dp[1]=1 |
| 746. 最小花费爬楼梯 | 最小代价 | dp[i]=min(dp[i-1]+c[i-1], dp[i-2]+c[i-2]) | dp[0]=0, dp[1]=0 |
✅ 三者关系图
Fibonacci → 爬楼梯 → 最小花费爬楼梯 （基础递推）（组合计数）（带权最优解）👉这是 DP 学习的标准演进路线
✅ 空间优化（进阶）
intprev2=0,prev1=0;for(inti=2;i<=cost.length;i++){intcurr=Math.min(prev1+cost[i-1],prev2+cost[i-2]);prev2=prev1;prev1=curr;}returnprev1;📌 面试一句话总结
这道题是“带权重的爬楼梯”，状态转移和斐波那契几乎一样，只是从求和变成了取最小值。