动态规划DP是算法面试的“深水区”也是无数人刷题之路的拦路虎。但DP的第一课并不难——LC.70爬楼梯和LC.509斐波那契数这两道“简单题”背后藏着DP的全部DNA重叠子问题、最优子结构、状态转移方程。今天我们不急着刷难题而是用这两道题把“DP五步曲”的思考框架一次讲透。这副骨架未来6天的每一道DP题都要往上挂。悬念先埋这两道题答案数列是同一个数列——爬到第3阶有3种方法恰好就是斐波那契的F(4)。为什么后面揭晓。 题目速览30 秒读懂题目1爬楼梯LC.70每次可以爬1或2个台阶问爬到第n阶有多少种不同的方法。示例n2 → 2 种11 或2示例n3 → 3 种111 / 12 / 21约束n ≤ 45。题目2斐波那契数LC.509F(0)0, F(1)1, F(n)F(n-1)F(n-2)。给定n求F(n)。约束n ≤ 30。 核心思路从暴力递归 → 记忆化 → 自底向上DP → 空间优化四步进化第一步先写暴力解——递归要爬到第n阶最后一步要么从n-1阶迈1步上来要么从n-2阶迈2步上来所以climb(n) climb(n-1) climb(n-2) 边界climb(1) 1, climb(2) 2这和斐波那契的定义一模一样。但复杂度是O(2^n)——n45时约350亿亿次调用直接超时。第二步为什么慢——重叠子问题画出递归树就明白了climb(5)分裂成climb(4)和climb(3)而climb(4)又分裂出climb(3)、climb(2)……同一个子问题被反复计算了无数遍。这些反复出现的子问题就叫重叠子问题Overlapping Subproblems——它是DP存在的第一理由。第三步记忆化——给重复计算加缓存既然climb(3)算过一次就是那个答案为什么还要再算用一个哈希表或数组把“已经算过的n → 结果”存起来递归入口先查缓存查到直接返回。这一改每个子问题只算一次复杂度从O(2^n)骤降到O(n)。这个技巧叫记忆化递归Memoization也就是俗称的“自顶向下的DP”。第四步自底向上DP 空间优化既然climb(n)只依赖climb(n-1)和climb(n-2)我们何必从n往下递归直接从1、2往上推先用1、2推出3再用2、3推出4……一路推到n。这就是自底向上Bottom-Up的DP即狭义的“动态规划”。它比记忆化递归少了函数调用开销和栈溢出风险还能顺手做空间优化。注意到推到第n项时只有前两项还有用更早的历史数据全是“死重”。用两个变量滚动替代整个数组空间降到O(1)。 DP五步曲刻进肌肉记忆状态定义dp[i]是什么含义爬到第i阶的方法总数状态转移方程dp[i]怎么由更小的状态推出dp[i] dp[i-1] dp[i-2]初始化最小规模的子问题答案是什么dp[1] 1, dp[2] 2遍历顺序从小到大保证算dp[i]时依赖项已就绪。返回答案dp[n]。悬念揭晓爬楼梯“最后一步是 1 阶还是 2 阶”的分类与斐波那契“前两项相加”的递推在数学上是同一个二阶线性递推——两道题本质是同一个数列。而记忆化递归与自底向上DP也不是两个算法而是同一个东西的两种写法前者自顶向下“用时才算”后者自底向上“提前算好”状态转移方程完全一致。️ 图解算法手把手走一遍暴力递归树n5重复子问题一眼可见climb(5) / \ climb(4) climb(3) ← climb(3) 第 1 次出现 / \ / \ climb(3) climb(2) climb(2) climb(1) / \ ↑重复 ↑重复 climb(2) climb(1) ... ↑重复climb(3)算2次、climb(2)算3次——n5已开始重复n 45时就是天文数字。记忆化之后每个节点只算一次树坍缩成一条链。自底向上DP表逐格填写n6idp[i]计算过程11初始化只有 1 步一种走法22初始化11 或 233dp[2]dp[1] 2145dp[3]dp[2] 3258dp[4]dp[3] 53613dp[5]dp[4] 85每一格都只看左边两格——这就是无后效性未来的计算只依赖已确定的过去与“怎么走到这一格”的路径无关。空间优化后DP表坍缩成两个滚动变量a1, b2 i1,2 的值 i3: (a,b) (2,3) i4: (a,b) (3,5) i5: (a,b) (5,8) i6: (a,b) (8,13) → 返回 b 代码实现Python Java四种写法全给Python版fromfunctoolsimportlru_cacheclassSolution:# 解法一记忆化递归自顶向下 DPdefclimbStairsMemo(self,n:int)-int:lru_cache(maxsizeNone)# lru_cache 即现成的记忆化缓存defclimb(k:int)-int:ifk2:# 边界dp[1]1, dp[2]2returnkreturnclimb(k-1)climb(k-2)# 转移方程returnclimb(n)# 解法二自底向上 DP 空间优化推荐defclimbStairs(self,n:int)-int:ifn2:returnn a,b1,2# adp[i-2], bdp[i-1]初始对应 dp[1], dp[2]for_inrange(3,n1):a,bb,ab# 滚动前进新 dp[i] dp[i-1] dp[i-2]returnb# 循环结束时 b 即 dp[n]Java版classSolution{// 解法一记忆化递归 privateInteger[]memo;// memo[i] 缓存爬到 i 阶的方法数publicintclimbStairsMemo(intn){memonewInteger[n1];returnclimb(n);}privateintclimb(intk){if(k2)returnk;// 边界if(memo[k]!null)returnmemo[k];// 查缓存算过直接返回memo[k]climb(k-1)climb(k-2);// 转移方程并存缓存returnmemo[k];}// 解法二自底向上 DP 空间优化推荐publicintclimbStairs(intn){if(n2)returnn;inta1,b2;// adp[i-2], bdp[i-1]for(inti3;in;i){intcab;// dp[i] dp[i-1] dp[i-2]ab;// 滚动更新bc;}returnb;// b 即 dp[n]}}⚠️关键提醒LC.509斐波那契数只需把边界改为F(0)0, F(1)1循环从2开始转移方程一字不改——两题同一个数列的代码级证据。⏱️ 复杂度分析面试必问方法时间空间说明暴力递归O(2^n)O(n)栈深度重复计算爆炸记忆化递归O(n)O(n)每个子问题算一次 缓存自底向上DPO(n)O(n)单层循环空间优化版O(n)O(1)两个滚动变量 举一反三3道高频变种题题目变化点思路调整LC.746 使用最小花费爬楼梯每阶有花费求最小总花费转移改为dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2])“方法数”变“最小值”LC.509 斐波那契数纯数列递推与爬楼梯同构改边界即可剑指 Offer10-II青蛙跳台阶与爬楼梯完全相同原题换皮注意取模 面试追问模拟提前准备Q1为什么朴素递归那么慢因为重叠子问题。递归树有O(2^n)个节点但不同的子问题只有n个剩下全是重复计算。DP的本质贡献就一句话让每个子问题只算一次。判断一个递归树是否“重复计算严重”是识别DP题的第一直觉。Q2怎么判断一个问题能不能用DP两个条件①最优子结构原问题的最优解能由子问题的最优解构造出来②重叠子问题递归展开时子问题反复出现。此外还有隐含的无后效性某状态一旦确定未来的决策不受“如何到达该状态”影响。三条齐备DP就是标配。Q3能更快吗O(logn) 呢可以矩阵快速幂。把递推写成矩阵形式[[1,1],[1,0]]^n用快速幂二分同款的“倍增”思想计算时间O(logn)。面试说出这个思路即可除非面试官要求手写矩阵乘法属于加分项而非必答题。 实战小技巧刷题党必备口诀先写暴力递归再画递归树找重复加缓存变记忆化倒过来推变DP。模板DP五步曲——状态定义、转移方程、初始化、遍历顺序、返回答案。防坑记忆化递归有栈溢出风险n大时优先自底向上。 实际应用场景不止是刷题机器人走网格路径计数每次向右或向下求总路径数骨牌铺满2×n地板方案数统计支付组合统计每次付1元或2元凑够n元有多少种付法组合数学/概率计数型DP是编程化的基础 今日思考题如果每次可以爬1、2或 3个台阶转移方程会变成什么提示dp[i] dp[i-1] dp[i-2] dp[i-3]初始化也要相应调整。你能把空间优化到O(1)吗
动态规划DP是算法面试的“深水区”也是无数人刷题之路的拦路虎。但DP的第一课并不难——LC.70爬楼梯和LC.509斐波那契数这两道“简单题”背后藏着DP的全部DNA重叠子问题、最优子结构、状态转移方程。今天我们不急着刷难题而是用这两道题把“DP五步曲”的思考框架一次讲透。这副骨架未来6天的每一道DP题都要往上挂。悬念先埋这两道题答案数列是同一个数列——爬到第3阶有3种方法恰好就是斐波那契的F(4)。为什么后面揭晓。 题目速览30 秒读懂题目1爬楼梯LC.70每次可以爬1或2个台阶问爬到第n阶有多少种不同的方法。示例n2 → 2 种11 或2示例n3 → 3 种111 / 12 / 21约束n ≤ 45。题目2斐波那契数LC.509F(0)0, F(1)1, F(n)F(n-1)F(n-2)。给定n求F(n)。约束n ≤ 30。 核心思路从暴力递归 → 记忆化 → 自底向上DP → 空间优化四步进化第一步先写暴力解——递归要爬到第n阶最后一步要么从n-1阶迈1步上来要么从n-2阶迈2步上来所以climb(n) climb(n-1) climb(n-2) 边界climb(1) 1, climb(2) 2这和斐波那契的定义一模一样。但复杂度是O(2^n)——n45时约350亿亿次调用直接超时。第二步为什么慢——重叠子问题画出递归树就明白了climb(5)分裂成climb(4)和climb(3)而climb(4)又分裂出climb(3)、climb(2)……同一个子问题被反复计算了无数遍。这些反复出现的子问题就叫重叠子问题Overlapping Subproblems——它是DP存在的第一理由。第三步记忆化——给重复计算加缓存既然climb(3)算过一次就是那个答案为什么还要再算用一个哈希表或数组把“已经算过的n → 结果”存起来递归入口先查缓存查到直接返回。这一改每个子问题只算一次复杂度从O(2^n)骤降到O(n)。这个技巧叫记忆化递归Memoization也就是俗称的“自顶向下的DP”。第四步自底向上DP 空间优化既然climb(n)只依赖climb(n-1)和climb(n-2)我们何必从n往下递归直接从1、2往上推先用1、2推出3再用2、3推出4……一路推到n。这就是自底向上Bottom-Up的DP即狭义的“动态规划”。它比记忆化递归少了函数调用开销和栈溢出风险还能顺手做空间优化。注意到推到第n项时只有前两项还有用更早的历史数据全是“死重”。用两个变量滚动替代整个数组空间降到O(1)。 DP五步曲刻进肌肉记忆状态定义dp[i]是什么含义爬到第i阶的方法总数状态转移方程dp[i]怎么由更小的状态推出dp[i] dp[i-1] dp[i-2]初始化最小规模的子问题答案是什么dp[1] 1, dp[2] 2遍历顺序从小到大保证算dp[i]时依赖项已就绪。返回答案dp[n]。悬念揭晓爬楼梯“最后一步是 1 阶还是 2 阶”的分类与斐波那契“前两项相加”的递推在数学上是同一个二阶线性递推——两道题本质是同一个数列。而记忆化递归与自底向上DP也不是两个算法而是同一个东西的两种写法前者自顶向下“用时才算”后者自底向上“提前算好”状态转移方程完全一致。️ 图解算法手把手走一遍暴力递归树n5重复子问题一眼可见climb(5) / \ climb(4) climb(3) ← climb(3) 第 1 次出现 / \ / \ climb(3) climb(2) climb(2) climb(1) / \ ↑重复 ↑重复 climb(2) climb(1) ... ↑重复climb(3)算2次、climb(2)算3次——n5已开始重复n 45时就是天文数字。记忆化之后每个节点只算一次树坍缩成一条链。自底向上DP表逐格填写n6idp[i]计算过程11初始化只有 1 步一种走法22初始化11 或 233dp[2]dp[1] 2145dp[3]dp[2] 3258dp[4]dp[3] 53613dp[5]dp[4] 85每一格都只看左边两格——这就是无后效性未来的计算只依赖已确定的过去与“怎么走到这一格”的路径无关。空间优化后DP表坍缩成两个滚动变量a1, b2 i1,2 的值 i3: (a,b) (2,3) i4: (a,b) (3,5) i5: (a,b) (5,8) i6: (a,b) (8,13) → 返回 b 代码实现Python Java四种写法全给Python版fromfunctoolsimportlru_cacheclassSolution:# 解法一记忆化递归自顶向下 DPdefclimbStairsMemo(self,n:int)-int:lru_cache(maxsizeNone)# lru_cache 即现成的记忆化缓存defclimb(k:int)-int:ifk2:# 边界dp[1]1, dp[2]2returnkreturnclimb(k-1)climb(k-2)# 转移方程returnclimb(n)# 解法二自底向上 DP 空间优化推荐defclimbStairs(self,n:int)-int:ifn2:returnn a,b1,2# adp[i-2], bdp[i-1]初始对应 dp[1], dp[2]for_inrange(3,n1):a,bb,ab# 滚动前进新 dp[i] dp[i-1] dp[i-2]returnb# 循环结束时 b 即 dp[n]Java版classSolution{// 解法一记忆化递归 privateInteger[]memo;// memo[i] 缓存爬到 i 阶的方法数publicintclimbStairsMemo(intn){memonewInteger[n1];returnclimb(n);}privateintclimb(intk){if(k2)returnk;// 边界if(memo[k]!null)returnmemo[k];// 查缓存算过直接返回memo[k]climb(k-1)climb(k-2);// 转移方程并存缓存returnmemo[k];}// 解法二自底向上 DP 空间优化推荐publicintclimbStairs(intn){if(n2)returnn;inta1,b2;// adp[i-2], bdp[i-1]for(inti3;in;i){intcab;// dp[i] dp[i-1] dp[i-2]ab;// 滚动更新bc;}returnb;// b 即 dp[n]}}⚠️关键提醒LC.509斐波那契数只需把边界改为F(0)0, F(1)1循环从2开始转移方程一字不改——两题同一个数列的代码级证据。⏱️ 复杂度分析面试必问方法时间空间说明暴力递归O(2^n)O(n)栈深度重复计算爆炸记忆化递归O(n)O(n)每个子问题算一次 缓存自底向上DPO(n)O(n)单层循环空间优化版O(n)O(1)两个滚动变量 举一反三3道高频变种题题目变化点思路调整LC.746 使用最小花费爬楼梯每阶有花费求最小总花费转移改为dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2])“方法数”变“最小值”LC.509 斐波那契数纯数列递推与爬楼梯同构改边界即可剑指 Offer10-II青蛙跳台阶与爬楼梯完全相同原题换皮注意取模 面试追问模拟提前准备Q1为什么朴素递归那么慢因为重叠子问题。递归树有O(2^n)个节点但不同的子问题只有n个剩下全是重复计算。DP的本质贡献就一句话让每个子问题只算一次。判断一个递归树是否“重复计算严重”是识别DP题的第一直觉。Q2怎么判断一个问题能不能用DP两个条件①最优子结构原问题的最优解能由子问题的最优解构造出来②重叠子问题递归展开时子问题反复出现。此外还有隐含的无后效性某状态一旦确定未来的决策不受“如何到达该状态”影响。三条齐备DP就是标配。Q3能更快吗O(logn) 呢可以矩阵快速幂。把递推写成矩阵形式[[1,1],[1,0]]^n用快速幂二分同款的“倍增”思想计算时间O(logn)。面试说出这个思路即可除非面试官要求手写矩阵乘法属于加分项而非必答题。 实战小技巧刷题党必备口诀先写暴力递归再画递归树找重复加缓存变记忆化倒过来推变DP。模板DP五步曲——状态定义、转移方程、初始化、遍历顺序、返回答案。防坑记忆化递归有栈溢出风险n大时优先自底向上。 实际应用场景不止是刷题机器人走网格路径计数每次向右或向下求总路径数骨牌铺满2×n地板方案数统计支付组合统计每次付1元或2元凑够n元有多少种付法组合数学/概率计数型DP是编程化的基础 今日思考题如果每次可以爬1、2或 3个台阶转移方程会变成什么提示dp[i] dp[i-1] dp[i-2] dp[i-3]初始化也要相应调整。你能把空间优化到O(1)吗
