切换主题
爬楼梯篇
爬楼梯
- 状态定义：
dp[i] = x，表示爬到第i阶有x种方法； base case：dp[0] = dp[1] = 1；- 状态转移方程：
dp[i] = dp[i-1] + dp[i-2]。
JavaScript
const climbStairs = n => {
let [dp0, dp1] = [1, 1]
for (let i = 2; i <= n; i++) {
[dp0, dp1] = [dp1, dp0 + dp1]
}
return dp1
}时间复杂度：O(n)；空间复杂度：O(1)。
使用最小花费爬楼梯
- 状态定义：
dp[i] = x，表示爬到第i阶最小需要花费x体力； base case：dp[0] = cost[0], dp[1] = cost[1]；- 状态转移方程：
dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i]。
JavaScript
const minCostClimbingStairs = cost => {
let dp0 = cost[0], dp1 = cost[1]
for (let i = 2; i < cost.length; i++) {
[dp0, dp1] = [dp1, Math.min(dp0, dp1) + cost[i]]
}
return Math.min(dp0, dp1)
}时间复杂度：O(n)；空间复杂度：O(1)。