引子老王的重复计算困惑还记得那位一路从查找江湖杀进图的世界、又拜入分治法门下、刚刚领悟了递归与回溯这对孪生引擎的老王吗这天老王正用刚学的递归兴致勃勃地算一道经典题——斐波那契数列每个数等于前两个数之和1、1、2、3、5、8、13……求第n个。他照着递归的套路唰唰写下第n个 第(n-1)个 第(n-2)个一直递归到第1个、第2个都是1就到底了。可当他真去算第50个时电脑却卡住了半天迟迟出不来结果老王纳闷极了扒开递归的过程一看顿时倒吸一口凉气算 第5个: 第5 ╱ ╲ 第4 第3 ← 算第5要算第4和第3 ╱ ╲ ╱ ╲ 第3 第2 第2 第1 ← 算第4又要算第3...第3被算了2次! ╱ ╲ 第2 第1 ← 越往下,重复越多!我的天!这递归看着优雅,实际笨得吓人**!**你看——算’第5个’要算’第3个’,算’第4个’又要算’第3个’……同一个’第3个’,被翻来覆去算了好多遍**!算到第50个,这种重复计算会爆炸式地堆成天文数字,电脑可不就卡死了嘛!**这明摆着的浪费——同一个答案,我明明算过一次了,干嘛还要傻乎乎地一遍遍重算?就不能把算过的答案记下来,下次直接拿来用吗?**老王这一拍桌子竟无师自通地撞上了算法世界里那座最负盛名、也最令人生畏的高峰——动态规划Dynamic Programming简称 DP。它的思想恰恰就藏在老王这句算过的答案干嘛要重算的灵光里像递归、分治一样把大问题拆成小问题大事化小但更进一步——把每个小问题的答案都记在一个小本本上下次再遇到同一个小问题直接翻本本拿答案绝不重算老王搓搓手“大事化小,再把小事的答案记在小本本上、绝不重复算……这思路,简直是给我那’又笨又慢的递归’,开了一剂’神药’啊!快说说,这’动态规划’到底咋个使法?”第一章DP的两大基石——“大事能拆小” “小事会重复”要用动态规划这剂神药得先看清一个问题配不配用它。动态规划专治那种同时具备两大特征的问题┌────────────────────────────────────────────────┐ │ 什么问题适合用动态规划?(两大基石,缺一不可) │ │ │ │ 基石① 最优子结构: │ │ 大问题的最优解,能由小问题的最优解拼出来 │ │ → 比如:第5个斐波那契第4个第3个 │ │ (大问题的答案,确实由小问题的答案组成!) │ │ │ │ 基石② 重叠子问题: │ │ 拆出来的小问题,会被反复、重复地用到 │ │ → 比如:第3个被算了一遍又一遍! │ │ → 正因为重复,才值得记下来省事! │ └────────────────────────────────────────────────┘看清门道了基石①最优子结构保证了大事能拆小、且拆了有用——大问题的答案确实能用小问题的答案拼出来基石②重叠子问题则是动态规划大显神威的根本原因——正因为小问题被反复重复地用到把它的答案记下来才划算如果每个小问题只用一次不重复那记下来也没意义那是分治法的地盘。老王恍然“原来如此!得是’大能拆小’(拼得出来),又’小事老重复’(值得记)——这两条都占了,动态规划才有用武之地!那斐波那契,正好两条全占!”第二章DP的灵魂——“小本本与填表”动态规划的核心操作朴素得就像填一张表格。我们就拿斐波那契开刀看看这剂神药怎么用核心思路准备一个小本本一张表 dp[]从最小的问题开始一个一个把答案算出来、记上去算大问题时直接翻本本拿现成的小答案绝不重算求斐波那契第7个,用小本本填表: dp[1] 1 ← 最小情况,直接写上(基石/出口) dp[2] 1 ← 最小情况,直接写上 dp[3] dp[2]dp[1] 11 2 ← 翻本本拿现成的! dp[4] dp[3]dp[2] 21 3 ← 翻本本拿现成的! dp[5] dp[4]dp[3] 32 5 dp[6] dp[5]dp[4] 53 8 dp[7] dp[6]dp[5] 85 13 ← 答案! 小本本:[ _, 1, 1, 2, 3, 5, 8, 13 ] ↑每个答案,只【算了一次】,记下就再没重算!天壤之别还记得递归算第5个时第3个被重复算了好多遍吗而用动态规划每个数,从小到大,老老实实只算一次,记在本本上算第50个、第100个也是啪啪啪一路填过去线性的速度眨眼就好——再不会像递归那样卡死了 这就是动态规划的灵魂用一点点记录答案的空间小本本“换来海量重复计算的时间”——这种用空间换时间的思想正是它化腐朽为神奇的根本老王拍案叫绝“妙啊!从小到大,一个一个填进小本本,每个只算一次,后面直接拿来用!那满天飞的重复计算,‘唰’地一下全没了!这’好记性’(小本本),可比我那’烂笔头加死脑筋’(纯递归)强太多了!”第三章经典实战——上楼梯有多少种走法光算斐波那契还不够过瘾。我们来看一道动态规划的入门经典题让老王彻底悟透如何把大事化小、列出递推关系——爬楼梯题目一段楼梯有 n 级台阶。你每次只能跨 1 级或跨 2 级。问爬到第 n 级总共有多少种不同的走法老王挠头直接想n级有多少种脑子乱成一团。别急用动态规划的思路去想最后一步┌────────────────────────────────────────────────┐ │ 关键一问:你是怎么迈上第n级的最后一步的? │ │ │ │ 只有两种可能! │ │ · 要么,从第(n-1)级,跨1步上来 → │ │ 那走法数 爬到第(n-1)级的走法数 │ │ · 要么,从第(n-2)级,跨2步上来 → │ │ 那走法数 爬到第(n-2)级的走法数 │ │ │ │ → 所以:到第n级的走法 到(n-1)级 到(n-2)级! │ │ dp[n] dp[n-1] dp[n-2] │ │ (咦?这递推关系,跟斐波那契一模一样!) │ └────────────────────────────────────────────────┘DP最精髓的思维解动态规划题最关键的就是想清楚——“大问题的答案怎么由更小问题的答案推出来”这就是状态转移方程。这里的窍门是去想最后一步是怎么来的——一拆大问题就漂亮地化成了小问题的和我们填表走一遍楼梯5级dp[1] 1 ← 爬到第1级,只有1种走法(跨1步) dp[2] 2 ← 爬到第2级:跨两个1步、或跨一个2步,2种 dp[3] dp[2]dp[1] 21 3 种 dp[4] dp[3]dp[2] 32 5 种 dp[5] dp[4]dp[3] 53 8 种 ← 答案! ┌────────────────────────────────────────────────┐ │ 爬5级楼梯,共有8种不同的走法! │ │ 靠的就是:想清最后一步→列出递推→从小填表到大! │ └────────────────────────────────────────────────┘老王看得连连点头“妙!直接想’5级有几种’想不明白,可一想’最后一步要么从第4级跨1步、要么从第3级跨2步上来’,这大问题’唰’地就拆成俩小问题了!再从小本本一路填上来,答案稳稳的!这’盯住最后一步’的窍门,真绝!”第四章DP三步走——解题的通用心法走了两道题老王想要个放之四海皆准的套路。我们就把动态规划的解题心法提炼成三步走┌────────────────────────────────────────────────┐ │ 动态规划解题三步走: │ │ │ │ ① 定义小本本(状态): │ │ 想清楚 dp[i] 到底代表第i个小问题的什么答案 │ │ (如:dp[i]爬到第i级的走法数) │ │ │ │ ② 找递推关系(状态转移方程): │ │ 想清楚 dp[大] 怎么由 dp[小] 们推出来 │ │ (常用窍门:想最后一步/最后一个是怎么来的) │ │ (如:dp[n]dp[n-1]dp[n-2]) │ │ │ │ ③ 定起点(初始值/边界): │ │ 最小的那几个问题,答案直接写死(出口) │ │ (如:dp[1]1, dp[2]2) │ │ │ │ → 然后:从小到大,一路填表,大功告成! │ └────────────────────────────────────────────────┘心法点睛解动态规划题最难、也最核心的是第②步——想出那个递推关系状态转移方程。一旦想通了大问题怎么由小问题拼出来剩下的填表就是水到渠成的体力活了。所以练DP练的就是那双’把大问题拆成小问题、并找出它们之间递推关系’的眼睛老王若有所悟“定本本、找递推、定起点,再从小填到大——套路清楚了!最难是’找递推’那一步,得动脑子想’大的咋由小的来’。这功夫,得多练!”第五章DP与递归——一对师出同门的对照老王心里有个疑惑这动态规划跟之前学的递归、分治到底啥关系我们把它们摆一起对照着看就透了┌──────────────┬────────────────────┬──────────────────────┐ │ │ 纯递归 │ 动态规划 │ ├──────────────┼────────────────────┼──────────────────────┤ │ 思路 │ 大事化小,自己调自己 │ 大事化小,但记下答案 │ │ 方向 │ 从大往小拆(自顶下)│ 从小往大填(自底上) │ │ 重复计算 │ 满天飞,重复算到爆 │ 每个只算一次,记本本 │ │ 速度 │ 可能慢到卡死(指数级)│ 飞快(通常线性级) │ │ 关系 │ DP常是加了小本本 │ 的、不重复计算的递归│ └──────────────┴────────────────────┴──────────────────────┘一语道破动态规划和递归本是师出同门——都靠大事化小。区别在于纯递归是从大往小拆拆的过程中一遍遍重复算同一个小问题所以慢动态规划则从小往大填把每个小问题的答案存进小本本绝不重算所以快。说白了动态规划 ≈ 递归大事化小 小本本记住答案、消灭重复计算它正是当初那个又笨又慢的递归的完美进化版老王彻底通透“原来它俩是亲兄弟!都是’大事化小’,只不过递归是’埋头往下拆、还老重算’,动态规划是’从小往上填、算过就记住’!这一记本本,就从’卡死’变’飞快’了!果然是递归的’升级神药’!”第六章终极总结——动态规划到底妙在哪老王把动态规划的智慧浓缩成一张表郑重地贴在了笔记本最显眼的位置┌────────────────┬──────────────────────────────────┐ │ 动态规划(DP) │ 说明 │ ├────────────────┼──────────────────────────────────┤ │ 核心思想 │ 大事化小把小事的答案记在小本本上 │ │ 两大基石 │ ①最优子结构(大解由小解拼) │ │ │ ②重叠子问题(小问题反复用,才值得记)│ │ 灵魂操作 │ 从小到大填表,每个答案只算一次 │ │ 解题三步 │ 定状态→找递推关系→定起点→填表 │ │ 最难一步 │ 找递推关系(想:最后一步咋来的) │ │ 本质 │ 用空间换时间(记答案,省重算) │ │ 与递归关系 │ ≈递归小本本,递归的进化版 │ │ 一句话 │ 算过的答案绝不重算,记下来一劳永逸!│ └────────────────┴──────────────────────────────────┘老王摸着这张表悟出了动态规划的题眼我总算把这座’最难的高峰’看透了——**它的根,还是’大事化小’;它的魂,却在那个’小本本’!面对一座大山,它先把山拆成小坡,可它比谁都精——每爬过一个小坡,就把这段路记在本本上;往后再遇到同一段,直接翻本本,绝不傻乎乎地重爬一遍!就靠这’算过一次,就记下来、绝不重算’的精明,它把递归那’卡到天荒地老’的重复苦活,一下压成了’从小到大、一路填表’的飞快活儿!原来,真正的高效,不只是会’把大事拆小’,更是有一本’好记性的小本本’——绝不让自己,在同一个地方,跌倒第二次、白费第二遍力气!尾声一本绝不重算的小本本亦是人生的智慧老王这场对动态规划的钻研从递归为何卡死的困惑出发看清了最优子结构重叠子问题两大基石领略了小本本填表、用空间换时间的精妙更看穿了它与递归师出同门、却青出于蓝的渊源——终于把算法世界里这座最负盛名的高峰也踩在了脚下。但当我们合上书会发现这一本绝不重算的小本本背后竟也舒展着几分耐人寻味的人生哲理。第一最大的浪费是在同一个地方反复跌倒、重复犯错。动态规划最深的智慧是它对重复计算那种近乎洁癖的厌恶——同一个小问题算过一次就牢牢记下绝不容许自己再傻算第二遍。正是消灭了这种重复劳动它才从卡死变得飞快。这何尝不是一记对人生的警钟我们一生中最大的浪费往往不是没努力而是在同一个坑里反复跌倒、为同一个错误反复买单、把同一段弯路走了一遍又一遍——同样的情绪内耗、同样的冲动决策、同样的轻信与受伤……每一次都从头重算却从不记在本本上。而真正在成长的人,都有一本动态规划式的’人生小本本’:每跌一次跤、踩一次坑、吃一次亏,都把教训郑重记下,内化成经验。于是同样的坑他绝不跌第二次同样的弯路他再不走第二遍。人和人拉开差距的,从不是谁没摔过跤,而是谁摔过之后,把它’记下来了’——绝不在同一处,白费第二遍力气。第二每一段走过的路都该沉淀成答案让未来一路通畅。动态规划之所以快是因为它走过的每一步都不是’用完即弃’的而是’沉淀’进了那个小本本成为后续大问题可以直接取用的基石。它从不孤立地解决问题而是让过去的每一个小答案都为未来的每一个大问题铺路。这是一种了不起的积累哲学。生活里有两种人一种人做事狗熊掰棒子做一件丢一件经验从不沉淀、知识从不归档、走过的路从不复盘于是永远在从零开始的低效里打转另一种人,像动态规划一样,把每一次的经历、思考、成果,都一点点’存进自己的小本本’——整理成方法、沉淀成体系、内化成本能。于是他后来的每一步,都站在’过去所有步’的肩膀上,越走越快、越走越高。别让走过的路白走——把每一段经历都沉淀成’下一次能直接调用的答案’,你的人生,才会像填表一样,一路通畅、加速向前。第三先想清大与小如何相连再动手——这是举重若轻的智慧。动态规划解题最关键的从不是埋头去算而是先静下心想透那个递推关系——想清楚大问题究竟怎么由小问题一步步拼出来。这一步想通了后面的填表便水到渠成。这给我们一个深刻的做事启示面对一桩庞大复杂的难事最忌讳的是’想都没想清楚,就一头扎进去蛮干’。真正的高手会先花力气去看清那个结构——这件大事是由哪些小事构成的它们之间是怎样层层递推、彼此支撑的想清了’大与小如何相连’这张图,再动手,便如庖丁解牛,顺着纹理,事半功倍。磨刀不误砍柴工——先看清结构、想透关系,再从最小处扎实做起、层层垒上去,是把’庞然大物’举重若轻地拿下的最聪明的姿势。下次当你面对一座望而生畏的难题或是发现自己又一次跌进了那个熟悉的坑里时请记得动态规划那本绝不重算的小本本——别让走过的路白走把每一次的教训与心得都郑重地’记在本本上’别急着埋头蛮干先想清楚’大事是怎么由小事拼成的’再从最小处一步步、踏踏实实地填上去。于是再难的高峰也终将在你绝不重复犯错、步步沉淀向上的从容里被一张表格平平稳稳地填到顶。“动态规划”就是这门关于绝不重复犯错、让经历沉淀成答案、先理清结构再动手的、朴素而深刻的智慧。它告诉我们最大的浪费是在同一个地方反复跌倒每一段走过的路都该沉淀成答案让未来一路通畅先想清大与小如何相连再动手是举重若轻的智慧。它像一句朴素的箴言提醒着我们——别在同一个坑里反复跌倒、为同一个错误反复买单——摔过的跤要记在本本上别让走过的路白走把每一段经历都沉淀成下一次能直接调用的答案别想都没想清就一头蛮干先看透大事如何由小事拼成再从最小处垒起——一个懂得不重复犯错、善沉淀积累、先理结构后动手的人才能像那本绝不重算的小本本纵使面对卡到天荒地老般的庞杂难题也总能举重若轻地把大山拆成小坡走过一段就记下一段绝不在同一处白费第二遍力气从最小处起步一路填表平平稳稳直抵山顶。这就是藏在动态规划背后那本绝不重算的小本本最深、也最美的浪漫。
