打卡到第三十七天训练营终于进入动态规划环节了。说实话此前我听到“动态规划”这四个字就一直有点发怵总觉得它比二叉树、回溯那些更抽象什么状态转移、重叠子问题、最优子结构听着全是术语。但真正把这一天安排的《代码随想录》三道题做完——509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯——我突然发现动态规划入门真的没有想象中那么难核心其实就是“把复杂问题拆成一步步的简单决策”前提是你得先把套路装进脑子里。这三道题在训练营里被放在一起不是没道理的。它们难度是平滑上升的第一道基本是照葫芦画瓢让你理解dp数组长什么样第二道把同样的思想套进一个具体场景第三道开始让你自己设计递推公式、处理边界。如果你能把这三天设计的三道题吃透后面背包问题、打家劫舍、股票问题再难骨架也都是今天打下的。这篇文章我不打算泛泛讲概念就按我做题时的真实思路把三道题从读题到AC的全过程拆开揉碎包括那些官方题解里一句带过、但你自己写代码容易卡住的地方。1. 训练营第三十七天动态规划终于来了在进入具体题目之前我想先聊聊代码随想录这套安排里最重要的一件事动态规划五部曲。Carl老师在书里反复强调的这套方法论我一开始觉得啰嗦不就是个循环吗后来被几道题打脸之后才老实按着步骤来。五部曲大概是这么个流程确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组验证正确性。这五步乍一看很像做题模板但真正做题时你会发现每一步都是一次决策。以509斐波那契数为例dp[i]是啥是第i个斐波那契数值。递推公式是啥题目直接给你了dp[i] dp[i - 1] dp[i - 2]。初始化题目也给了dp[0] 0dp[1] 1。遍历顺序呢因为dp[i]依赖前面的数据所以从左往右。最后拿n5跑一遍0,1,1,2,3,5完全对上。你可能觉得这太简单了但注意这套流程的价值不在于“验证简单题”而在于当你面对一道完全没见过的题时至少有一个不变的抓手。很多同学一拿到动态规划题就懵其实不是不会写代码而是跳过了第一步和第二步直接想“我要怎么遍历出答案”这就是典型的次序反了。dp数组的含义没定清楚后面的公式、初始化、遍历方向全是空中楼阁。所以这三道题真正的训练目标不是让你学会“斐波那契”“爬楼梯”这两个具体问题而是让你把五部曲内化成一种条件反射。后面做01背包时容量、价值、物品之间的关系比这复杂得多但只要你每一步都有意识地“定含义、写公式、做初始化、定遍历、做验证”至少不会完全没方向。还有一点我想特别指出动态规划题的核心往往就是那一个递推公式但如果你只背公式下次换个壳就认不出来了。三道题里第二题爬楼梯的公式和第一题斐波那契一模一样第三题则变成了求最小值。这种“同骨架、不同血肉”的设计就是在逼你理解公式是怎么来的而不是记公式本身。所以下面我会把每道题的推导过程写得细一点尤其是“为什么是这样”而不是“是什么”。2. 509. 斐波那契数动态规划最朴素的骨架2.1 为什么暴力递归是个反面教材先看题目斐波那契数通常用 F(n) 表示F(0) 0F(1) 1F(n) F(n - 1) F(n - 2)n 2。给定 n计算 F(n)。这道题刚接触算法的人第一反应肯定是递归因为题目描述本身就是递归定义的。代码写出来也就三五行def fib(n): if n 1: return n return fib(n - 1) fib(n - 2)但你去提交就会发现n只要稍微大一点比如35、40就会慢得让人抓狂甚至直接超时。原因是这个递归做了大量的重复计算。以fib(5)为例fib(5)调用fib(4)和fib(3)fib(4)又调用fib(3)和fib(2)这里fib(3)就被算了两次往下fib(2)、fib(1)会被重复算更多次。节点数量是2^n级别的时间复杂度妥妥O(2^n)。我们常说动态规划能优化“重叠子问题”斐波那契是最直观的例子。同一个子问题被反复求解这就是重叠子问题而动态规划的思路就是“算一次、存起来后面直接用”。这跟我们平时写代码做缓存是一个道理只不过动态规划把它抽象成了一套系统的状态转移方法。2.2 dp数组与递推公式一步都不能跳按照五部曲来第一步确定dp数组的含义。dp[i]表示第i个斐波那契数的值。这一步看起来废话但它是整道题的地基。你可以试试在不写dp数组的情况下只用两个变量滚动求值当然也能做出来但那就不好理解递推到底是什么了。训练阶段先把dp数组写完整把过程看清楚。第二步递推公式。这题没什么悬念dp[i] dp[i - 1] dp[i - 2]。但我建议你认真体会一下“当前状态依赖前两个状态”这句话。一个状态的推导只依赖前面紧挨着的两个状态这种结构后面会反复出现爬楼梯是它最小花费爬楼梯也是它只是加了一个min取最小值。你可以先把这种“链式状态依赖”焊死在脑子里。第三步初始化。dp[0] 0dp[1] 1这两个值不依赖任何其他状态是递推的起点。千万不要从dp[2]开始初始化那会导致取值逻辑混乱。第四步遍历顺序。因为每个dp[i]都依赖dp[i-1]和dp[i-2]所以必须从小到大、从前往后算。如果从n往0倒着遍历那dp[i-1]和dp[i-2]根本还没算出来就乱套了。第五步举例推导。这是很多人偷懒的一步但我建议你就算n6也要手写一遍0、1、1、2、3、5、8跟正确答案对一下确认思路没问题再写代码。尤其是面试场景下这一套“推导自检”会让你出错概率大大降低。2.3 完整代码与滚动数组优化先把不那么抠空间的版本写出来class Solution { 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]; } }这段代码提交没问题时间复杂度O(n)空间复杂度O(n)。但如果问到空间优化我们可以继续想既然每个dp[i]只依赖前两个状态那整个dp数组里真正有用的其实只有“前一个状态”和“前前一个状态”。用三个变量滚动更新就能把空间压到O(1)class Solution { public int fib(int n) { if (n 1) return n; int a 0, b 1; for (int i 2; i n; i) { int sum a b; a b; b sum; } return b; } }这里的a、b分别对应dp[i-2]和dp[i-1]每一轮循环算完当前值后整体向后滑动一位。我第一次看到这个写法时觉得“哇好妙”但实际上它就是“发现状态依赖关系后做空间压缩”的典型结果后面爬楼梯、最小花费爬楼梯同样适用。所以不要把这三种变量当成什么特殊技巧它只是动态规划递推关系的自然推论。3. 70. 爬楼梯当斐波那契变成了场景题3.1 为什么最后一步决定了整个递推关系第二题是爬楼梯假设你正在爬楼梯需要n阶才能到达楼顶每次你可以爬1阶或2阶问有多少种不同的方法可以爬到楼顶n是正整数。这题第一眼和斐波那契完全不像但做起来就会发现选择题感极强。这里的突破口是思考“最后一步”。我要爬到第n阶最后一步可能是从第n-1阶跨1阶上来的也可能是从第n-2阶跨2阶上来的。这两种情况互不重叠而且覆盖了所有可能。于是问题就转化成了爬到第n阶的方法数 爬到第n-1阶的方法数 爬到第n-2阶的方法数。设dp[i]为爬到第i阶的方法数那么dp[i] dp[i-1] dp[i-2]你看递推公式跟斐波那契一模一样。但为什么说它是“场景题”因为它的dp含义不再是“第几个数的值”而是“到达某个状态的方法数”。你需要自己从题目描述里抽象出这个状态。这类“计数类动态规划”在算法面试里非常多见而爬楼梯是最经典的入门载体。如果能想明白“最后一步法”后面很多路径问题、跳跃问题都会轻松不少。3.2 初始化是个容易翻车的细节这里有个很有迷惑性的点斐波那契的初值是dp[0]0、dp[1]1爬楼梯的初值该怎么设题目说n是正整数那至少有一阶。既然是正整数我们直接从dp[1]开始讨论更有意义dp[1] 1只有一阶台阶只能爬1阶就一种方法dp[2] 2两阶台阶可以一次跨2阶也可以分两次各跨1阶两种方法。然后从i3开始递推。很多照着斐波那契思路写的人会把dp[0]也设为1说“0阶就是不动一种方法”逻辑上说得通但容易把初学者绕晕。我建议训练阶段就把dp[0]先放一边只初始化dp[1]和dp[2]这样每一步推导都有具体的现实含义不容易出错。等到你真的理解了再去考虑需不需要纠结dp[0]的语义。还有一个小细节如果n是1直接返回dp[1]1别让循环去访问dp[2]所以循环前要加个if判断。这类边界条件在LeetCode上往往是最容易导致提交失败的一定要养成“写完循环先看一眼边界”的习惯。3.3 手动推导一遍n5彻底理解递推我们来手推一下n5的情况看看dp数组是怎么一步步长大的dp[1] 1dp[2] 2dp[3] dp[2] dp[1] 2 1 3对应111、12、21三种方法dp[4] dp[3] dp[2] 3 2 5对应1111、112、121、211、22五种dp[5] dp[4] dp[3] 5 3 8。8种方法你可以穷举一下确实是8种。这个推导过程没用到任何复杂数学就是纯粹的“状态累加”。我当时做的时候还特意把n4的5种爬法全列出来发现跟dp数组完全对得上那一刻才对递推公式有了真实的信任感而不是“背下来还能用”。下面是常规代码class Solution { 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]; } }空间优化版本跟斐波那契的滚动数组一个套路用两个变量就够了这里不重复贴重点在于理解为什么可以这么省空间。3.4 为什么它和斐波那契有同样的公式这里我想多聊一句公式相同但意义不同这件事。斐波那契的F(n) F(n-1) F(n-2)是题目直接给的数学定义而爬楼梯的dp[i] dp[i-1] dp[i-2]是“从最后一步分类讨论”推出来的计数关系。两者的数学结构一样但推导逻辑完全不同。这也是为什么训练营会把这两道题连在一起你要学会的不是“见过这个公式”而是“在陌生的场景里发现熟悉的公式”。这种能力在动态规划里比任何技巧都重要。后面遇到“不同路径”“整数拆分”这些题同样是用分类讨论的方式去寻找状态之间的关系只是分类的维度更多了。现在爬楼梯练的就是单一维度的分类把这一层想透后面复用起来才有根。4. 746. 使用最小花费爬楼梯动态规划开始讲成本了4.1 先读懂题意到底哪里是楼顶第三题就稍微反过来考你了给你一个整数数组cost其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。你一次可以爬一个或两个台阶可以从下标为0或1的台阶开始爬。问到达“楼梯顶部”的最低花费是多少。我第一次做这题就栽在“楼顶”的理解上。很多题解直接说“楼顶是下标为n的位置”但没解释为什么。这里的关键是cost数组的长度是n下标是0到n-1代表n个台阶。你爬完第n-1个台阶之后还需要再上一级才能到达顶部所以楼顶是下标n一个超出数组长度的位置。换句话说返回的是dp[n]而不是dp[n-1]。这一下就把dp数组的下标含义定清楚了dp[i]表示到达下标为i的台阶所需的最小花费。i的取值范围是0到n其中in表示楼顶。想清楚这个再往下做才不会出现“少一级”的错误。4.2 递推公式从加法变成了求最小值还是用“最后一步”的思路。要到达下标i这一阶只有两种可能从i-1阶跨一步上来花费是到达i-1阶的最小花费加上cost[i-1]从i-2阶跨两步上来花费是到达i-2阶的最小花费加上cost[i-2]。因为我们要求最小花费所以两者取更小的那个。递推公式就变成了dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])注意这里的cost下标跟dp下标错开了。dp[i]和cost[i]不是同一种东西dp[i]是“到达i的累计花费”cost[i]是“从i出发时的花费”。很多新手写代码时容易把cost下标写成cost[i]结果越界或者逻辑全错原因就是对“状态”和“动作花费”的区分不够清楚。你可以把cost想成“上车的费用”dp想成“到这里已经花了多少钱”二者计量对象完全不同。4.3 初始化与不初始化哪个更安全题目明确说“可以从下标为0或1的台阶开始爬”意思是你不用为起步支付任何费用站在0号台阶或1号台阶时花费都是0。所以dp[0] 0dp[1] 0。这一步推导特别重要因为它天然处理了“选择起点”的需求。如果你把dp[0]和dp[1]初始化为cost[0]和cost[1]那就等于强行要求必须先付起步费用但题目说的是“开始爬”之后才需要支付当前台阶的向上费用起步台阶不需要付费。我见过不少题解在这个地方含糊代码跑起来也能过一部分测试用例但遇到特殊数据就会出问题。还有个更让人迷惑的点为什么dp[1]前没有台阶也要初始化成0因为题目允许直接站在1号台阶。这里体现的是动态规划初始化“要覆盖所有合法起点”的原则。你回头再看爬楼梯起点只有1号台阶一种因为必须从地面开始爬而这道题的起点有两种所以初始化要考虑两种情况。求最小值的递推代码class Solution { 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]; } }这里我建议不要急着做滚动数组优化先把dp数组完整打印出来看一遍。以cost [10, 15, 20]为例dp[2] min(dp[1] 15, dp[0] 10) min(15, 10) 10意思是到2号台阶最低花10块dp[3] min(dp[2] 20, dp[1] 15) min(30, 15) 15所以到楼顶最少花15路径是“站上1号台阶跨两步直接到楼顶”。不打印数组你很难直观看见这个决策过程。再提一个细节有人会把递推写成dp[i] min(dp[i-1], dp[i-2]) cost[i]然后返回min(dp[n-1], dp[n-2])这种写法定义的是“到达i并支付从i出发的费用”其实也能做对但容易在返回值和下标上晕。我自己的经验是dp含义越贴近“累计花费”代码越不容易出边界错。5. 三道题里最容易踩的坑与滚动数组优化5.1 边界条件与LeetCode交作业的惨痛经验三道题做完你会发现几乎所有的WA都出在几个类似位置一是n太小循环还没开始就return了二是cost数组长度为0或1题目虽然保证至少有一个元素但思维上还是要过一遍三是把dp[n]和dp[n-1]搞混尤其是第三题。这里我说一个自己比较惨痛的教训做746的时候我一开始想着“楼顶是最后一个台阶”于是把dp数组长度定义成了n返回dp[n-1]提交之后样例就挂了一个。后来我把样例cost[10,15,20]的每一步dp打出来才发现那个额外的一级台阶太关键了。从那以后我养成了一个习惯拿到动态规划题先花半分钟回答三个问题——状态从哪个下标开始状态到哪个下标结束返回的到底是哪个下标这三个问题想明白边界错误能减少八成。5.2 滚动数组省空间不是炫技是顺理成章三道题的递推都只依赖dp[i-1]和dp[i-2]所以整个dp数组在时间上可以压缩成几个变量。很多人一看到“滚动数组”“空间复杂度O(1)”就觉得是高阶技巧其实它只说明一件事你的状态转移只关心有限个历史状态。以746为例跑通dp数组版本之后可以优化成这样class Solution { public int minCostClimbingStairs(int[] cost) { int n cost.length; int dp0 0; int dp1 0; for (int i 2; i n; i) { int temp Math.min(dp1 cost[i - 1], dp0 cost[i - 2]); dp0 dp1; dp1 temp; } return dp1; } }这段代码唯一的难点是对着下标手挪变量。我自己的经验是先画一条数轴标出dp0和dp1分别代表dp[i-2]和dp[i-1]每轮循环里算出新的“当前状态”后整体向后滑动。不要靠记忆硬写画一遍比背十遍管用。5.3 三道题的状态设计与初始条件对照把三道题放在一起看状态设计从简洁到复杂的变化非常明显题目dp[i]含义递推公式初始化注意点509.斐波那契数第i个斐波那契值dp[i] dp[i-1] dp[i-2]dp[0]0, dp[1]1公式由题目直接给定70.爬楼梯爬到第i阶的方法数dp[i] dp[i-1] dp[i-2]dp[1]1, dp[2]2由最后一步分类推导计数746.使用最小花费爬楼梯到达第i阶的最小花费dp[i] min(dp[i-1]cost[i-1], dp[i-2]cost[i-2])dp[0]0, dp[1]0楼顶下标为n不是n-1从这张表能看到一个规律递推公式其实都是在回答“当前状态能由哪些前置状态以什么代价转换而来”。斐波那契的代价是0爬楼梯的代价是每种方式计1个方法最小花费的代价是具体的cost数值。理解了这个“状态转换”视角动态规划的千变万化对你来说就统一了。6. 做完这一天三道题我复盘出的做题方法论坦白说第三十七天这三道题放在整个训练营里属于“前菜”级别但它们的训练价值恰恰在于让你用最小的复杂度去内化动态规划的核心思维。我做完之后复盘总结出几个方法论层面的东西分享给你参考。第一永远先定义dp数组再想别的。以前我总喜欢先想“用什么数据结构”“怎么遍历”现在反过来先把dp[i]的一句话定义写在草稿纸上写得越精确越好。比如不是“dp表示答案”而是“dp[i]表示到达第i个台阶的最小累计花费”。定义越具体后面越难跑偏。第二递推公式的推导靠“最后一步分类讨论”。不管是方法数、路径数、最小代价都问自己一句到达目标状态的最后一步有哪些可能每种可能对应什么前置状态把这些可能性加起来或者取最小公式就出来了。这个思路在爬楼梯和最小花费爬楼梯里体现得淋漓尽致。第三初始化不是拍脑袋而是要回答“哪些状态不需要递推就能确定”。斐波那契的0和1是定义给的爬楼梯的1和2是实际情况给的746的0和0是题目约定给的。初始化永远跟着题目的实际约束走不能套模板。第四边界条件要用具体小例子去验。写完代码别急着提交先拿n0、n1、n2或者长度为1、2的cost数组在脑子里跑一遍确认循环不会访问不存在的下标。别看这一步琐碎我大部分提交失败都栽在这里。第五空间优化可以锦上添花但不能本末倒置。训练阶段建议先老老实实写dp数组把状态演化过程打印出来彻底理解了递推关系之后再去改滚动数组。如果一上来就追求O(1)空间代码是短了但你对“状态”的理解可能就模糊了。面试的时候也一样先给出清晰的O(n)版本再主动优化到O(1)这比一上来写个自己也解释不清的滚动数组要加分得多。最后再分享一个小技巧。我做这三道题时养成了“一道题至少手推一个小案例”的习惯哪怕这个案例只有n4或者cost长度等于3。手推的过程其实是在模拟计算机执行它能逼你发现那些“想当然”的逻辑漏洞。比如我手推746的cost[10,15,20]时才发现最优路径是起点选1号台阶直接跨两步而不是从0号开始走这一步的理解直接让我避开了把dp[1]初始化成cost[1]的错误。动态规划这扇门对我来说就是从这一天真正打开的。后面还有01背包、完全背包、打家劫舍、股票问题这些硬仗但核心的思维方式已经在这里扎下根了。如果看完这篇你也在跟这三道题较劲我的建议很简单别急着看题解先拿纸笔把五部曲一步步写下来尤其是亲手推导一遍递推过程。你会发现那些看起来“高深”的动态规划其实也就是把小事算对、算清楚而已。