1. 动态规划入门为什么这三道题一定要放在一起刷如果你正在跟着代码随想录刷算法或者自己在力扣上按专题整理题目大概率会在某个阶段同时撞见509斐波那契数、70爬楼梯、746使用最小花费爬楼梯这三道题。它们看起来一个比一个简单甚至斐波那契数在很多人眼里就是一道“递归热身题”但说实话这三道题恰恰是理解动态规划最核心逻辑的黄金组合。先说结论这三道题几乎覆盖了动态规划入门阶段最重要的几个要素——状态定义、递推公式、初始化、遍历顺序、以及“到底要不要多开一个位置”这种看似不起眼却决定生死的小细节。很多同学刷到后面遇到复杂DP就懵其实不是智商问题而是入门阶段没有把这几道题吃透。我见过太多人上来就背“dp[i] dp[i-1] dp[i-2]”却说不清为什么爬楼梯是斐波那契、为什么最小花费爬楼梯要把dp数组初始化成那样。这种状态刷一百道题也是白搭。这篇文章不是单纯把三份题解贴在一起而是想以“动态规划五部曲”为主线把三道题串联起来讲清楚DP的底层思考方式。不管你是零基础刚接触DP还是刷了一阵子但总觉得隔层纱都建议把这三道题当成一个整体反复咀嚼尤其是746那道题它其实是检验你有没有真正理解“状态定义”的试金石。2. DP五部曲你真正需要记的并不是状态转移方程很多新手学动态规划最大的误区就是盯着递推公式看觉得“公式都看不懂还做个屁”。实际上动态规划里最值钱的从来不是那个公式本身而是怎么一步步推导出公式的过程。这里我按代码随想录的习惯整理成五步每一步都不能跳确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组验证是否合理。这五个步骤里真正决定一道DP题生死的是第一步“状态定义”以及第三步“初始化”。因为递推公式很多人看一眼就会初始化才是最容易翻车的地方。比如斐波那契数你当然知道dp[0]0、dp[1]1但如果你把dp数组定义成“前i个数的和”那初始化就会变成另一个人故事公式也全乱套。这就是为什么我强烈建议你把这三道题放一起刷它们的状态定义非常相似却又有着微妙差异正好用来训练“先定义状态、再写公式”的肌肉记忆。2.1 第一道最经典的509斐波那契数斐波那契数本身并不难通项公式就写在题目里F(0)0F(1)1F(n)F(n-1)F(n-2)。但如果你想拿它练习DP就别一上来就写递归。递归解法在这个问题上复杂度是O(2^n)n稍微一大就卡成PPT更重要的是递归思路和DP思路是两种完全不同的思维模式。用五部曲拆解确定dp数组及含义dp[i]表示第i个斐波那契数值。确定递推公式dp[i] dp[i-1] dp[i-2]。初始化dp[0] 0dp[1] 1。遍历顺序显然从i2开始从前向后遍历。举例推导n5时dp数组依次为0,1,1,2,3,5。这里有一个值得记录的细节其实你并不需要维护整个dp数组因为递推公式只管前两个状态。所以工程上完全可以用两个变量滚动更新把空间复杂度从O(n)压到O(1)。很多人在这一步会纠结“到底要不要省空间”我的建议是刷题初期先把完整dp数组写清楚确保自己每一步都能打印出来验证把正确率稳固之后再谈优化。一上来就写滚动变量很容易把自己绕晕尤其在遇到746那种边界条件比较多的题目时更容易翻车。写得稍快一点就能拿出类似这样的代码def fib(n): if n 1: return n dp [0] * (n 1) dp[0] 0 dp[1] 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]这段代码就是最朴素的DP模板。先把数组建出来再初始化再遍历填表最后返回目标值。几乎所有入门DP题都可以按这个框架套。2.2 爬楼梯为什么它和斐波那契数长得如此像70爬楼梯在很多人的记忆里跟斐波那契数“几乎一摸一样”但如果你只是机械地把公式抄过来就错过了一次绝佳的“状态定义训练”。题目说你每次可以爬1个或2个台阶问爬到第n阶有多少种不同的方法。关键在于你怎么理解“方法数”这件事。走到第n阶最后一步要么是从第n-1阶跨1步上来要么是从第n-2阶跨2步上来。所以到达第n阶的总方法数就等于到达第n-1阶的方法数加上到达第n-2阶的方法数。至此递推公式浮出水面dp[i] dp[i-1] dp[i-2]。这里请你注意这个递推公式和斐波那契数一模一样但状态定义完全不同斐波那契数里dp[i]是“数值”爬楼梯里dp[i]是“方法数”。正是这种“公式一样但含义不同”的题目最适合拿来检验你是否真的理解了DP而不是死记硬背。最经典的坑是初始化斐波那契数从F(0)0、F(1)1开始而爬楼梯通常初始化dp[1]1、dp[2]2。如果你非要从dp[0]开始推就需要额外解释dp[0]应该等于多少。很多题解会直接写dp[0]1因为从第0阶出发到第0阶只有一种方式——不爬。这个解释在逻辑上自洽但对初学者来说问“0阶怎么会有1种方法”比问“1阶当然只有1种”要玄学得多。所以我的习惯是在爬楼梯这个问题上直接初始化dp[1]1、dp[2]2然后从i3开始遍历。这样每一步都可以用生活常识验证不需要额外解释dp[0]这种边界位置。def climb_stairs(n): if n 2: return n dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]你可能会问那如果题目改成一次可以爬1、2、3阶呢其实递推公式就会变成dp[i] dp[i-1] dp[i-2] dp[i-3]初始化又多一个dp[3]4。这类变体在面试里很常见改法就是“最后一跳能跨几阶就回头加几个dp值”。理解到这一层爬楼梯这类题就算真正吃透了。2.3 最小花费爬楼梯状态定义一偏全盘皆输746这道题绝对是三道题里最容易让人栽跟头的。它的难点不在于递推公式有多复杂而在于大家对“爬到楼顶”这件事的理解不一致。题目给了一个cost数组cost[i]代表从第i个台阶向上爬需要支付的费用。你可以从下标为0或1的台阶开始爬每次可以爬一个或两个台阶问爬到楼梯顶部的最小花费是多少。请注意这道题里“到达第i个台阶”和“从第i个台阶出发”是两回事。如果你把dp[i]定义成“到达第i个台阶的最小花费”那你到达楼顶时其实没有“从楼顶出发”的花费需要在最后一步做额外判断如果你把dp[i]定义成“从第i个台阶出发向上爬所需的最小总花费”那递推的方向、初始化的位置都会跟着变而且代码反而更绕。我还是推荐代码随想录里最常用的定义方式dp[i]表示到达第i个台阶所需要的最小花费。那么要到达第i个台阶只有两种可能从第i-1个台阶跨1步过来或者从第i-2个台阶跨2步过来。前者的花费是dp[i-1] cost[i-1]后者的花费是dp[i-2] cost[i-2]。取最小值就得到dp[i] min(dp[i-1] cost[i-1], dp[i-2] cost[i-2])初始化部分是最容易出问题的。题目允许从下标0或1开始爬这意味着到达第0个台阶和第1个台阶都不需要花费所以dp[0]0、dp[1]0。千万别把cost[0]或cost[1]直接塞进去那样相当于“还没出发就先付钱”逻辑上就错了。def min_cost_climbing_stairs(cost): n len(cost) dp [0] * (n 1) dp[0] 0 dp[1] 0 for i in range(2, n 1): dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]) return dp[n]看到这里你应该已经能感受到这道题和前面两道的差别斐波那契数和爬楼梯dp[i]只依赖前面的两个dp值而746的dp[i]除了依赖dp值还额外依赖cost数组里的值。这一步看似只是公式里多了个cost但它意味着你在定义状态时必须把“花费发生在哪一步”想清楚。很多人卡在这道题上根本原因不是不会写min而是没想明白“到达第i阶”和“从第i阶出发”到底谁是dp的主角。有一个经典翻车例子有人把dp[i]定义成“从第i阶出发到楼顶的最小花费”然后从后往前遍历。这样写也不是不行但初始化会变成dp[n]0、dp[n-1]cost[n-1]遍历方向全反过来。一旦dp数组下标和cost数组下标错位代码分分钟ArrayIndexOutOfBounds。所以我一直建议初学者别在这个阶段追求“另一种定义方式”先把一种主流定义吃透等理解深入了再尝试反向写法。3. 从递归到DP为什么递归能做的事DP非要再来一遍这三道题都可以用递归直接写尤其斐波那契数递归代码短得令人发指。比如def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)这段代码确实好写但它有一个致命问题重复计算。你算fib(5)需要fib(4)和fib(3)算fib(4)又需要fib(3)和fib(2)。于是fib(3)被算了至少两次fib(2)更多次。n10还能忍n40就开始卡顿n100就直接爆炸。复杂度大约是O(2^n)指数级增长面试官看到这种写法大概率会追问一句“能不能优化”。递归加个字典做记忆化memoization确实能把复杂度降到O(n)但本质上是“自顶向下”的思考方式仍然带着递归调用的栈开销。而DP的“自底向上”思路是直接从最小子问题开始一层层往上填表省掉了递归调用栈也让整个计算过程变得可追踪、可调试。在实际工程里自底向上的迭代往往更稳定也更容易做空间优化。所以刷这三道题的意义不只是把题解AC掉而是让你亲身感受“同样的数学关系用递归写和用DP写差别有多大”。我特别建议你做一个简单的小实验分别用纯递归、记忆化递归、DP三种方式跑fib(35)看看耗时差异。这个实验做完你对“为什么需要DP”这件事的理解会比看十篇理论文章都深刻。这里再多说一句递归不是不好它在很多场景下依然是极其优雅的解法尤其是在树的遍历里。但在涉及大量重叠子问题的场景下DP明显是更合适的方案。理解两者的适用边界比二选一更重要。4. 从这道题延伸出去背包问题、打家劫舍、股票问题到底难在哪当你把509、70、746这三道题吃透后会发现自己站在一个很微妙的分岔路口一边是朴素的线性DP一边是背包、打家劫舍、股票买卖这些“看起来每个字都认识、但就是写不出来”的进阶题目。很多人刷到这里就会崩溃因为代码随想录训练营的节奏非常紧凑今天还在爬楼梯明天突然就跳到01背包。但其实你回头想想所有进阶DP题本质上都在做同样的五件事定义状态、找递推公式、初始化、确定遍历顺序、举例验证。那为什么背包问题会难那么多因为它的dp数组含义不再是“第i个位置上是什么”而是“在i个物品下容量为j时能装的最大价值”。这等于多了一个维度dp数组从一维变成二维。理解不了二维DP的人往往是因为在一维DP阶段就没有把“状态定义”这个地基打好。而爬楼梯和最小花费爬楼梯恰好是练习一维状态定义的绝佳素材。打家劫舍也是一样。它告诉你不能偷相邻的房子于是“偷不偷当前房子”这个决策改变了状态定义。你会发现递推公式变成了dp[i] max(dp[i-1], dp[i-2] nums[i])其中dp[i-1]表示不偷当前房子dp[i-2]nums[i]表示偷当前房子。这比爬楼梯多了一个“决策”维度。但如果你把爬楼梯的“到达第i阶只有两种来源”想得足够清楚打家劫舍的“选择当前和不选择当前”也能顺理成章地理解。我不建议你在没有吃透这三道题之前就跑去刷背包那样只会打击信心。但反过来如果你能把这三道题讲给别人听讲清楚为什么爬楼梯和斐波那契数的公式一样但含义不同讲清楚为什么746的dp[0]和dp[1]都要初始化成0那你已经具备了理解二维DP最基本的思维框架。剩下的只是多练、多体会。5. 实操过程全记录我用三种语言把三题跑通很多人刷题只看题解不敲代码这是最大的忌讳。我自己带训练营的经验是一道题至少要亲手敲两遍第一遍看着题解敲第二遍合上题解自己敲。敲完还要跑用例、打日志、甚至故意改错几处来观察报错信息这样才算真正过了一遍脑子。下面我把三道题的完整实操过程记录下来按Python、Java、C三种常见语言各写一版顺便标出语言层面的坑。5.1 斐波那契数三种语言实现Python版本def fib(n): a, b 0, 1 for _ in range(n): a, b b, a b return a这里用滚动变量直接求第n项循环结束后a就是第n项。这个写法非常Pythonic但注意range(n)的边界n0时循环不执行直接返回0正好符合题目。Java版本public int fib(int n) { if (n 1) return n; int[] dp new int[n 1]; dp[0] 0; dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; }Java里数组默认初始化为0所以dp[0]可以不用显式赋值但建议写上方便阅读。n0时new int[1]不会越界直接返回0没问题。C版本int fib(int n) { if (n 1) return n; vectorint dp(n 1); dp[0] 0; dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; }C的vector同样默认初始化但用vector需要包含头文件。如果你追求极致空间优化可以只维护两个int。5.2 爬楼梯三种语言实现Python版本def climb_stairs(n): if n 2: return n dp [0] * (n 1) dp[1], dp[2] 1, 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]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]; }C版本int climbStairs(int n) { if (n 2) return n; vectorint dp(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]; }三个版本几乎一样这就是线性DP的典型特征语言差异只体现在语法层面核心逻辑完全一致。5.3 最小花费爬楼梯三种语言实现Python版本def min_cost_climbing_stairs(cost): n len(cost) dp [0] * (n 1) dp[0] dp[1] 0 for i in range(2, n 1): dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]) return dp[n]Java版本public int minCostClimbingStairs(int[] cost) { int n cost.length; int[] dp new int[n 1]; dp[0] 0; dp[1] 0; for (int i 2; i n; i) { dp[i] Math.min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]); } return dp[n]; }C版本int minCostClimbingStairs(vectorint cost) { int n cost.size(); vectorint dp(n 1); dp[0] 0; dp[1] 0; for (int i 2; i n; i) { dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]); } return dp[n]; }这三份代码里最容易出错的点是dp数组的长度。因为题目要爬到顶顶的位置在数组下标n处所以dp长度必须是n1。如果你写成dp长度等于cost.length那么返回dp[n-1]其实只是到达最后一个台阶的位置并没有到楼顶。这个细节我要特意强调因为真的有很多人在这一步少算了一格。5.4 空间优化什么时候该用滚动数组上面所有代码都可以做空间优化核心思想是既然dp[i]只依赖前两个状态那何必留一整个数组用两个变量滚动覆盖即可。以746为例优化后可以写成def min_cost_climbing_stairs(cost): n len(cost) prev2 0 prev1 0 for i in range(2, n 1): cur min(prev1 cost[i - 1], prev2 cost[i - 2]) prev2 prev1 prev1 cur return prev1这段代码执行效率很高空间O(1)但阅读门槛比完整dp数组高一些。我的建议是如果你是在笔试或面试中写代码优先写完整dp数组版本因为清晰、不容易错如果你是想把代码优化到极致再用滚动数组。面试官通常更看重你能不能把思路讲清楚而不是空间复杂度那一点差别。5.5 实操中的三个常见误区误区一下标越界。Java和C里访问数组越界会直接抛异常或者产生未定义行为。很多人在746这道题里写循环时把i的起点设成1然后访问dp[i-2]瞬间越界。正确做法是先想清楚dp[0]、dp[1]已经初始化循环从i2开始。误区二把“到达楼顶”和“到达最后一个台阶”混为一谈。爬楼梯的楼顶是第n阶所以dp[n]才是答案最小花费爬楼梯的楼顶是越过所有台阶所以答案同样在dp[n]n等于cost数组长度不是cost长度减1。误区三初始化时直接把cost值填进dp。比如有人写dp[0]cost[0]、dp[1]cost[1]这完全偏离了状态定义。题目明明说可以从第0或第1个台阶开始爬也就是说刚站上这两个台阶还没“向上爬”当然不应该先花一笔钱。6. 常见问题与排查技巧实录我在带训练营和帮朋友纠错的过程中遇到过不少反复出现的报错和困惑这里整理成一张速查表方便你对照排查。症状可能原因解决办法爬楼梯n3结果返回3但n4结果不对dp[0]初始化逻辑混乱改用dp[1]1、dp[2]2的初始化方式从i3开始遍历最小花费爬楼梯返回的数字比预期小dp[0]和dp[1]被错误填成cost值dp[0]0、dp[1]0出发前不花钱数组越界访问ArrayIndexOutOfBoundsdp数组长度设成了cost.lengthdp长度设为cost.length1楼顶位置在n斐波那契数n0时返回空数组或抛异常没有处理n1的边界加if n 1: return n空间优化版代码结果和完整dp版不一致更新prev1、prev2的顺序写反了先计算cur再赋值prev2prev1最后prev1curJava版本中new int[n1]但n0数组长度为1没问题但要注意dp[1]会越界循环前加if n 1判断除了这张表我再分享一个排查技巧每次写完DP先在脑子里手动模拟一遍长度为3或4的cost数组把dp数组的每一步计算过程写在纸上。比如cost [10, 15, 20]dp[2]应该等于min(dp[1]15, dp[0]10)10dp[3]应该等于min(dp[2]20, dp[1]10)min(1020, 010)10。所以最小花费是10对应先走两步到第2阶花费010再走一步到楼顶花费20等等这里要重新算。我把这个例子完整展开一下。cost [10, 15, 20]n3。dp[0]0、dp[1]0。i2dp[2] min(dp[1]cost[1], dp[0]cost[0]) min(015, 010) 10。i3dp[3] min(dp[2]cost[2], dp[1]cost[1]) min(1020, 015) 15。所以答案15。这个例子里最优路径是先跨两步直接到第2阶花费0再跨一步到楼顶花费cost[2]20那加起来应该是20为什么dp[3]是15注意这里的dp[2]是到达第2阶的最小花费10它对应的路径是从第0阶跨两步直接到第2阶跳过第1阶不花cost[0]cost[1]而是只花cost[0]10。所以在dp[3]计算里dp[2]cost[2]102030。而另一个选择dp[1]cost[1]01515意思是先到第1阶不花钱再从第1阶跨一步到楼顶花cost[1]15。所以答案是15。这个例子非常典型因为它揭示了一个事实“最小花费”不一定非得从最后一个台阶跨一步上去也可能从倒数第二个台阶跨两步直接跳上顶。这就是为什么dp[n]要在两个来源里取最小值。手动模拟这么一遍之后很多看起来神神秘秘的DP题都会变得特别透明。这也是我一直强调的不要只在脑子里想拿笔写一遍dp数组推导过程比看十遍代码管用。另一个排查技巧是加日志打印。在循环里打印i、dp[i-1]、cost[i-1]、dp[i-2]、cost[i-2]你就能直观看到每一步取min到底选了哪个分支。尤其是当你怀疑自己的逻辑“好像对但答案总差一点”的时候打印日志是最快的定位方式。还有人问我这三道题到底有没有必要做进阶变体。我的回答是非常有必要。你可以自己试着改题——把爬楼梯改成“可以爬1、2、3阶”把最小花费爬楼梯改成“可以从任意偶数下标开始爬”甚至把cost数组改成二维。每改一个条件你都要重新审视状态定义和递推公式这就是最好的DP训练。在我个人的算法训练经验里509、70、746这三道题就像酿酒前的三颗葡萄。单独吃味道平平放在一起反复咀嚼你会发现它们共同构成了动态规划入门最重要的味觉基础。很多年后你面对复杂的编辑距离、正则表达式匹配、股票交易冷冻期回头再看这三道题依然会觉得它们是整个DP体系里最干净、最经典的起点。最后再分享一个小技巧如果你在训练营里跟着打卡强烈建议每题都写一篇“题目小结”哪怕只有三五行也行。写下来之后你会发现当时觉得想不明白的点在写成文字的过程中突然就通了。我的好多题解初稿其实就是训练营里随手写下的几句碎碎念后来慢慢扩展成了完整文章。刷题别只为了AC留点记录路会越走越宽。