1. 从采药这道题看动态规划的入门门槛第一次在题库里翻到采药这道题的人十有八九会愣一下题目名字挺文艺点进去一看其实就是个背包问题。它几乎是所有算法学习者绕不开的一道经典题也是很多人第一次真正理解0-1背包这个模型的起点。我见过太多人在这一题上卡了整整一个下午不是因为题目有多难而是因为从暴力枚举到动态规划这一步思维跳跃没人给他们讲透。这道题的核心场景很朴素你有一个容量固定的背包题目里叫采药的时间面前有一堆草药每株草药有采摘需要花费的时间和它自身的价值每株草药只能采一次问在限定时间内能获得的最大总价值。听起来是不是特别像给你一个固定大小的箱子让你装东西怎么装最值钱对这就是最标准的0-1背包问题。它适合谁来啃如果你是刚学完递归、正在往动态规划过渡的阶段这道题就是你的最佳练手对象。如果你已经会写背包但总是记不住状态转移方程这道题可以帮你把原理彻底焊死在脑子里。哪怕你只是想在面试前快速复习一下DP的经典模型这道题也值得你花二十分钟重新推一遍。我写这篇东西的目的很简单把这道题从看题解能懂、自己写就废的状态变成闭着眼睛都能推出来的状态。下面我会从暴力解法讲起一步步推到一维数组优化再把里面那些容易踩的坑一个个挖出来给你看。2. 暴力枚举为什么一定会超时先算一笔账2.1 每株草药采或不采的决策树先别急着上DP。我们来看看最直觉的做法对于每一株草药我们都有两个选择——采它或者不采它。如果有n株草药那总共就有2的n次方种组合。题目里n最大可以到100有些版本是10002的100次方是什么概念大约是1.27乘以10的30次方。就算你的电脑每秒能处理一亿种情况算完也要花上比宇宙年龄还长的时间。这就是为什么暴力枚举在n稍微大一点的时候就彻底不可行了。但理解暴力解法非常重要因为它揭示了问题的本质结构这是一个多阶段决策问题。每走到一株草药面前你都要做一次决策而这个决策会影响后面还能不能采别的草药因为时间被消耗了。2.2 用递归把决策过程写出来我们可以用递归来模拟这个过程。定义函数dfs(i, t)表示考虑到第i株草药当前还剩t的时间能获得的最大价值。那么对于第i株草药如果采它前提是t time[i]那么收益是value[i] dfs(i1, t - time[i])如果不采它收益是dfs(i1, t)两者取最大值就是当前状态的最优解。这个递归思路完全正确但问题在于它会重复计算大量相同的子问题。比如还剩50时间、考虑到第30株草药这个状态可能会被从不同的路径反复到达。这就是重叠子问题也是动态规划能够生效的前提。我实测过当n30左右的时候纯递归就已经明显卡顿了。n40的时候基本要等好几秒。所以暴力递归只能用来验证小数据量的正确性不能作为最终提交的代码。2.3 记忆化搜索从递归到DP的桥梁在纯递归的基础上加一个记忆数组就变成了记忆化搜索。具体做法是开一个二维数组memo[i][t]初始值设为-1表示这个状态还没算过。每次进入dfs(i, t)之前先检查memo[i][t]是否已经有值有的话直接返回没有的话算完再存进去。这一步的改动极小但效果是质变。因为每个状态(i, t)最多只会被真正计算一次总的状态数是n * Tn是草药数量T是总时间时间复杂度直接降到了O(nT)。对于n100、T1000的规模也就是十万次计算瞬间出结果。记忆化搜索的好处是思维负担小——你不需要去考虑遍历顺序不需要去想要不要倒序循环只要把递归逻辑写对加个缓存就完事了。对于刚接触DP的人来说这是最友好的入门方式。但它也有缺点递归深度受限于系统栈n特别大的时候可能会爆栈。所以实际比赛中大家更倾向于写成递推形式。3. 二维DP的状态定义与转移方程推导3.1 状态定义dp[i][j]到底代表什么从记忆化搜索自然过渡到递推我们就得到了二维DP的写法。定义dp[i][j]表示从前i株草药中选择在时间不超过j的前提下能获得的最大价值。注意这里的措辞——从前i株中选择不是必须选第i株。这个区别非常关键很多人写转移方程的时候搞混了这一点导致漏掉不选第i株的情况。状态定义的准确性直接决定了转移方程能不能写对。我个人的经验是每次写DP之前先用一句完整的中文把dp[i][j]的含义念出来念得通顺了再动手写代码。如果这句话你自己念着都觉得别扭那大概率定义有问题。3.2 转移方程的两种写法基于上面的定义对于第i株草药注意下标从1开始我们有两种选择不选第i株那么最大价值就是dp[i-1][j]也就是从前i-1株里选、时间限制还是j的最优解。选第i株前提是j time[i]那么价值是dp[i-1][j - time[i]] value[i]。意思是先从前i-1株里选时间限制缩小到j - time[i]然后再加上第i株的价值。所以转移方程是dp[i][j] dp[i-1][j] if (j time[i]) dp[i][j] max(dp[i][j], dp[i-1][j - time[i]] value[i])这里有一个细节值得展开说为什么选第i株的时候前面部分用的是dp[i-1]而不是dp[i]因为每株草药只能采一次。如果用dp[i][j - time[i]]那就意味着第i株可以被重复选取那就变成了完全背包问题。这个区别是0-1背包和完全背包的核心分界线一定要记牢。3.3 边界条件与初始化dp[0][j]表示从前0株草药中选那自然是什么都选不了价值为0。所以第一行全部初始化为0。同理dp[i][0]表示时间限制为0也什么都采不了价值也是0。这里有一个容易犯的错误有人会把dp数组全部初始化为0然后发现答案是对的就以为初始化不重要。在0-1背包求最大值的场景下全部初始化为0确实没问题因为什么都不选本身就是合法状态价值为0。但如果题目改成恰好装满背包或者求最小值初始化就需要特别处理了。这个坑我在后面会详细讲。3.4 遍历顺序为什么外层循环是物品、内层是容量二维DP的遍历顺序相对自由。你可以外层循环物品、内层循环容量也可以反过来。只要保证计算dp[i][j]的时候它依赖的状态dp[i-1][j]和dp[i-1][j - time[i]]已经被算出来了就行。但通常我们选择外层循环物品、内层循环容量因为这样更容易理解也更容易过渡到一维优化。内层循环容量的时候从小到大或者从大到小都可以因为二维数组里每一行是独立的不会互相覆盖。我个人的习惯是内层也从小到大遍历这样写出来的代码和转移方程的对应关系最直观。等你熟悉了之后可以尝试不同的遍历顺序加深对状态依赖关系的理解。4. 一维数组优化空间从O(nT)降到O(T)4.1 滚动数组的核心思想二维DP的空间复杂度是O(nT)。当n1000、T10000的时候就是一千萬个int大约40MB。虽然大多数题目不会卡这个空间但能省则省而且一维写法更简洁。观察转移方程dp[i][j]只依赖于dp[i-1]这一行的数据和更早的行没有关系。这意味着我们不需要保存整个二维表只需要保存上一行和当前行就够了。进一步想如果我们把内层循环改成从大到小遍历容量那么dp[j - time[i]]访问的就是上一行的值因为还没被当前物品更新过我们就可以直接用一个一维数组搞定。这就是滚动数组的精髓用倒序遍历来保证每个物品只被使用一次。4.2 倒序遍历的具体操作与验证一维写法的代码是这样的for (int i 1; i n; i) { for (int j T; j time[i]; j--) { dp[j] max(dp[j], dp[j - time[i]] value[i]); } }关键点在于内层循环j从T递减到time[i]。为什么必须倒序假设我们正序遍历当计算dp[j]的时候dp[j - time[i]]可能已经在本次物品的循环中被更新过了那就意味着第i株草药被选了两次变成了完全背包。倒序遍历则保证dp[j - time[i]]还是上一轮即前i-1株的值不会被污染。这个点我在初学的时候反复搞混过。后来我养成了一个习惯每次写一维背包先在纸上画一个简单的例子手动模拟一遍正序和倒序的区别确认自己真的理解了再写代码。这个方法看起来很笨但确实有效。4.3 一维写法的边界与常见错误一维写法有一个常见的错误内层循环的终止条件写成j 0或者j 0。如果j time[i]那么j - time[i]就是负数数组越界。所以终止条件必须是j time[i]。另一个错误是外层循环和内层循环写反。如果外层循环容量、内层循环物品那就变成了完全背包的写法每个物品可以被选多次。这个错误非常隐蔽因为对于某些测试数据答案可能碰巧是对的但换一组数据就错了。提示写完一维背包后一定要用一组小数据手动模拟一遍确认每个物品只被选了一次。这是避免0-1背包写成完全背包的最有效方法。5. 从采药延伸到背包问题的几个变种5.1 恰好装满与求最小值的初始化差异采药这道题求的是时间不超过T的最大价值属于不超过类型。如果题目改成恰好花完T时间能获得的最大价值初始化就要变。具体来说dp[0] 0其他dp[j]初始化为负无穷。这样做的原因是只有容量为0的状态是恰好装满的合法状态其他容量在没有任何物品时是不可能恰好装满的。同理如果求的是恰好装满时的最小价值初始化就是dp[0] 0其他为正无穷。如果求不超过T的最小价值那所有dp[j]初始化为0即可。这个初始化规则我总结成一句话求最大值时不合法的状态设为负无穷求最小值时不合法的状态设为正无穷如果什么都不选是合法状态那初始值就是0。这句话几乎适用于所有背包变种。5.2 完全背包与多重背包的识别如果每株草药可以采无限次那就是完全背包一维写法内层循环改成正序即可。如果每株草药有数量限制比如最多采k次那就是多重背包可以用二进制拆分或者单调队列优化。在实际题目中识别背包类型的关键是看每个物品的使用次数。0-1背包每个物品用0次或1次完全背包用无限次多重背包用有限次。识别对了类型代码框架基本就定了。5.3 分组背包与依赖背包的简单介绍分组背包是指物品被分成若干组每组最多选一个。这种问题的做法是外层循环组、内层循环容量、最内层循环组内物品。依赖背包是指物品之间有依赖关系比如选A必须先选B这种问题通常可以转化为树形DP或者用拓扑排序预处理。采药这道题本身不涉及这些变种但它是理解所有这些变种的基础。我建议你在彻底搞懂采药之后去找几道完全背包和多重背包的题目练手感受一下代码框架的微调。6. 实测中的性能对比与调试技巧6.1 不同解法的运行时间实测我拿n100、T1000的数据做了一组实测结果如下解法时间复杂度运行时间约空间复杂度纯递归O(2^n)超时10秒O(n)记忆化搜索O(nT)约2msO(nT)二维递推O(nT)约1msO(nT)一维滚动O(nT)约1msO(T)可以看到从递归到记忆化搜索是质的飞跃而从二维到一维主要是空间上的优化时间上差别不大。所以在实际比赛中如果空间够用二维写法更不容易出错如果空间紧张再考虑一维写法。6.2 用对拍验证正确性写DP最怕的就是样例过了但隐藏数据挂了。我的做法是写一个暴力递归版本作为标准答案然后随机生成小规模数据n15T100用两个程序分别跑对比结果。如果连续几百组数据都一致那基本可以放心了。对拍脚本可以用Python写也可以用shell脚本。核心思路就是生成随机输入 - 分别运行两个程序 - 比较输出 - 不一致就停下来看数据。这个技巧不仅适用于背包问题适用于所有算法题。6.3 调试DP的实用方法DP的调试比普通程序麻烦因为状态多、转移复杂。我的经验是打印DP表。对于小规模数据把整个二维DP表打印出来人工检查几个关键位置的值是否符合预期。比如dp[1][time[1]]应该等于value[1]dp[1][time[1]-1]应该等于0。如果这些基本位置都不对那说明转移方程或者初始化有问题。另一个方法是在转移方程里加断言。比如在更新dp[i][j]之前断言dp[i-1][j]已经被计算过。虽然正式提交的时候要去掉断言但调试阶段非常有用。7. 我在教别人写这道题时总结的几个经验教过不少人写这道题之后我发现大家卡住的地方高度集中。第一个坎是不理解状态定义很多人能背出转移方程但你问他dp[i][j]是什么意思他答不上来。我的建议是在写代码之前先用注释把状态定义写在代码最上面写不清楚就别动手。第二个坎是搞混遍历顺序。二维DP的遍历顺序相对自由但一维DP的内层必须倒序。这个点我强调过无数次但还是有人写错。后来我想了个办法让他们在代码里加一行注释// 倒序遍历保证每个物品只选一次写代码之前先写注释慢慢就形成条件反射了。第三个坎是初始化搞错。尤其是从不超过变到恰好装满的时候很多人忘了改初始化导致答案偏大或偏小。我的建议是每次写背包之前先问自己三个问题——求最大值还是最小值是不超过还是恰好什么都不选是不是合法状态这三个问题的答案决定了初始化方式。最后一个经验是关于刷题策略的。很多人做完采药就去做完全背包结果发现代码几乎一样但就是过不了。我的建议是做完一道背包题之后不要急着做下一道先把这道题的代码改一改试试改成完全背包、改成恰好装满、改成求最小值看看能不能自己推出来。这种一题多改的练习方式比刷十道新题都管用。注意背包问题的变种非常多但核心框架就那几行。把一道题吃透比泛泛地刷一百道题更有价值。我在实际学习中最大的体会就是慢就是快少就是多。