知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 02 - 爬楼梯 ## 题目(LeetCode 70) 每次可以爬 1 或 2 个台阶,爬到第 n 阶有多少种方法? ``` 输入:n = 5 输出:8 ``` ## 先搞清楚:为什么是"加法"而不是"乘法"? ``` 到第 n 阶,最后一步要么爬了 1 阶,要么爬了 2 阶: 最后爬 1 阶:之前在第 n-1 阶,有 dp[n-1] 种方法到达 n-1 阶 最后爬 2 阶:之前在第 n-2 阶,有 dp[n-2] 种方法到达 n-2 阶 这两种情况是互斥的(要么最后爬 1 步,要么最后爬 2 步,不能同时) 互斥事件的总数 = 各自数量相加 所以 dp[n] = dp[n-1] + dp[n-2] ``` ## 大白话理解 想象你站在楼梯底部,每次可以迈 1 步或 2 步。 ``` 到第 1 阶:只有 1 种方法(迈 1 步) 到第 2 阶:有 2 种方法(1+1 或 2) 到第 3 阶:有 3 种方法(1+1+1, 1+2, 2+1) 到第 4 阶:有 5 种方法 到第 5 阶:有 8 种方法 规律:dp[n] = dp[n-1] + dp[n-2],就是斐波那契数列! ``` ### 为什么是斐波那契? ``` 到第 n 阶的方法 = 从第 n-1 阶迈 1 步的方法 + 从第 n-2 阶迈 2 步的方法 = dp[n-1] + dp[n-2] 这和斐波那契的递推公式完全一样,只是初始值不同: 斐波那契:f(0)=0, f(1)=1 爬楼梯: dp[1]=1, dp[2]=2 ``` ## 决策树(n=4) ``` 到第 4 阶的所有路径: 第 4 阶 / \ 最后爬1步 最后爬2步 第 3 阶 第 2 阶 / \ / \ 最后1步 最后2步 最后1步 最后2步 第 2 阶 第 1 阶 第 1 阶 第 0 阶 / \ | | | 最后1步 最后2步 最后1步 最后1步 (起点) 第1阶 第0阶 第0阶 第0阶 路径(从下往上读): 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 共 5 种 ✓ ``` ## 手动模拟(n=5) ``` dp[1] = 1(只有一种:迈 1 步) dp[2] = 2(两种:1+1 或 2) i=3: dp[3] = dp[2] + dp[1] = 2 + 1 = 3 三种方法:1+1+1, 1+2, 2+1 i=4: dp[4] = dp[3] + dp[2] = 3 + 2 = 5 五种方法:1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 i=5: dp[5] = dp[4] + dp[3] = 5 + 3 = 8 八种方法: 1+1+1+1+1 1+1+1+2 1+1+2+1 1+2+1+1 2+1+1+1 1+2+2 2+1+2 2+2+1 答案 = 8 ✓ ``` ## 代码 ### 写法 1:DP 数组 ```java public int climbStairs(int n) { if (n <= 2) return n; int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } ``` ### 写法 2:空间优化(只用两个变量) ``` dp[i] 只依赖 dp[i-1] 和 dp[i-2],不需要整个数组 用两个变量滚动更新就行 ``` ```java public int climbStairs(int n) { if (n <= 2) return n; int prev2 = 1, prev1 = 2; for (int i = 3; i <= n; i++) { int curr = prev1 + prev2; prev2 = prev1; prev1 = curr; } return prev1; } ``` ### 空间优化的手动模拟(n=5) ``` 初始:prev2 = 1(dp[1]),prev1 = 2(dp[2]) i=3: curr = 2 + 1 = 3 → prev2=2, prev1=3 i=4: curr = 3 + 2 = 5 → prev2=3, prev1=5 i=5: curr = 5 + 3 = 8 → prev2=5, prev1=8 返回 prev1 = 8 ✓ ``` ## 注意:容易困惑的地方 ``` Q:为什么 dp[1]=1, dp[2]=2,而不是 dp[0]=0, dp[1]=1(斐波那契的初始值)? A:爬楼梯的初始值和斐波那契不同: dp[1]=1:到第 1 阶有 1 种方法 dp[2]=2:到第 2 阶有 2 种方法(1+1 或 2) 如果用斐波那契的初始值 dp[0]=0, dp[1]=1,结果会差 1。 Q:如果每次可以爬 1、2 或 3 步怎么办? A:dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 初始值:dp[1]=1, dp[2]=2, dp[3]=4 代码改成三个变量滚动更新即可。 ``` ## 一句话总结 dp[i] = dp[i-1] + dp[i-2],就是斐波那契数列。空间优化到两个变量。 --- 上一篇:[01 - DP框架](./01-dp-framework.md) | 下一篇:[03 - 打家劫舍](./03-house-robber.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入