企业官网建设流程全解析

“更弱智的算法学习”这个系列写到第20天，我自己都有点意外。前19天磕磕绊绊搞完了数组、链表、哈希、栈队列、递归、二分、双指针、排序，还有简单的DFS和贪心入门。按大多数人的学习路径，到这会儿可以硬着头皮上动态规划了，但我在动手之前先说清楚：今天这篇不是那种“状态转移方程拍脸上让你背”的文章，我用的还是这个系列最擅长的“弱智学习法”——先把高深术语翻译成人话，再用人话把代码写出来，最后才回头对号入座去补术语。动态规划这四个字，听起来像是什么高深的数学魔法，但等你看完斐波那契和爬楼梯的推导过程，你会发现它本质上就是“聪明的枚举”，一个在你小学奥数或者日常点菜时就已经在用的小技巧。

如果你是零基础、以前一看“动态规划”就头大，或者哪怕你已经刷过几道题但始终是“看答案秒懂，自己写就卡壳”，这篇文章应该能帮你把这层窗户纸捅破。我们先不急着谈“最优子结构”“无后效性”这些吓人的名词，我会用第20天这个节点上的思维进度，把从暴力递归到动态规划的推导链路完整走一遍，再拿两个经典问题现场演示。看完你会发现：动态规划真不是什么高智商专属，它就是一个有套路、能套模板、能一步步推出来的思考方法。

1. 第20天的心态与准备：前面19天到底练了什么

这个系列叫“更弱智的算法学习”，不是我自贬，是真的在找一个更适合普通人的学习节奏。市面上很多资料默认你是科班、默认你数学底子好、默认你是天才，然后一上来就扔给你状态转移方程。我怕的不是你看不懂，怕的是你看完“哦，原来如此”，合上书自己动手时依然是零。

所以前19天我做的所有事，都是在给第20天铺路。我在第7天花了一整篇讲递归，原因很简单：动态规划的题没有递归基础根本讲不透。你可以这么理解，动态规划就是从暴力递归里长出来的东西。如果你递归还没搞懂，可以先回去翻翻之前那篇，或者随便找一道递归题练练手，但今天你至少要知道“函数调用自己”是怎么回事。

到第19天为止，我给自己梳理了一个简单的进度表，你也可以照这个路线走：

你会发现，我没有直接照搬大学算法课的顺序，而是把一个普通人的学习路径重新排了一遍。贪心放在了DFS前面，动态规划放在了DFS后面。这其实是有讲究的：贪心让你理解什么是“局部最优”，DFS让你理解什么是“状态的探索”，有了这两个基础，动态规划的“状态定义”和“状态转移”才不会像凭空冒出来一样。

另外，第20天这个节点还有一个心理因素。连续打卡20天，最怕的不是不会，而是“会的都做完了，开始碰钉子”。动态规划天生就是劝退者，它不像二分查找那样规则简单，也不像BFS那样套路固定。如果你已经在这个位置，恭喜你，说明你已经啃下了前面所有基础模块，具备研究动态规划的脑力带宽了。如果还没到这个位置，也没关系，看完今天的再回去补，也不冲突。

2. 动态规划不是玄学：从暴力递归到记忆化搜索的完整推导链路

很多教程讲动态规划，上来就给你dp数组、状态定义、转移方程，然后让你背。但我的实验结论是：正常人根本背不住，就算背住了也不会用。我自己第20天尝试了一个更笨但更能从根上理解的方法——先写暴力递归，然后看它坐下了哪些重复劳动，再把重复劳动的结果记下来，最后把“记下来”这件事从递归里抽出来。

第一步：用斐波那契数列感受一下什么是暴力。斐波那契的数学定义大家基本都知道：fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2)。如果按定义直接写成递归，代码长这样：

def fib(n: int) -> int: if n <= 1: return n return fib(n - 1) + fib(n - 2)

这段代码本身没毛病，简洁到不能再简洁。但如果你跑fib(40)，会明显感觉卡顿。为什么？我当初看别人的分析时只记住了“指数级复杂度”这个结论，直到我自己画出调用树才真正理解。你算fib(6)的时候，会发现它去求了fib(5)和fib(4)，而fib(5)又会去求fib(4)和fib(3)。注意，fib(4)算了不止一遍，fib(3)算的遍数更多，越往底层，重复计算的次数越夸张。

这就是“重叠子问题”，它有个很生活化的解释：你今天做米饭，要打电话问妈妈放多少水；明天做米饭，又打电话问妈妈放多少水。你明明昨天已经问过了，今天完全可以把这个答案记在冰箱贴上面。暴力递归就是“每次都重新打电话问”，动态规划就是“第一次问了之后记下来，之后直接看冰箱贴”。

第二步，我们用“冰箱贴”优化递归。这个“冰箱贴”在代码里叫备忘录，一般用一个数组或字典实现：

def fib(n: int, memo: dict) -> int: if n in memo: return memo[n] if n <= 1: return n memo[n] = fib(n - 1, memo) + fib(n - 2, memo) return memo[n]

加了这三行代码，同样的fib(6)，每个子问题只计算一次，复杂度从指数级降到O(n)。这个版本有个名字，叫“记忆化搜索”或者“带备忘录的自顶向下递归”。这已经是动态规划的“近亲”了，但还不是最终形态。

第三步，把“自顶向下递归”改写成“自底向上递推”。递归是从上往下问，先问fib(6)要什么，一层层往下拆。递推是反过来，我先算最小的fib(0)和fib(1)，然后推出fib(2)、fib(3)，一步步推到fib(6)。改写成数组递推之后，这就是教科书上说的“正宗动态规划”：

def fib(n: int) -> int: if n <= 1: return n dp = [0] * (n + 1) dp[0], dp[1] = 0, 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]

很多人到这里就没下文了，但是我建议你亲自把这三步各写一遍，运行一遍，看看耗时差距。等你真的感受到暴力递归怎么一步步变聪明，你就会理解为什么动态规划不是玄学——它就是“把递归过程中重复计算的结果缓存起来，并且改成从前往后推”。

说到这里，必须先做一个名词澄清。动态规划最常见的标签有两个：“重叠子问题”和“最优子结构”。斐波那契完美演示了“重叠子问题”，但它没有“选择”，所以还不是完整意义上的动态规划。真正经典的动态规划题，往往还有一个“选还是不选”的决策过程，比如后面要讲的0-1背包。我建议你先把斐波那契这条推导链路彻底看懂，因为它承载了“状态”“转移”“初始化”三个最基本概念的雏形。

3. 这三个核心概念，我用生活常识硬生生啃下来的

很多教程讲到动态规划会直接甩出“状态”“状态转移方程”“边界条件”三件套，搞得像黑话。第20天我决定换一种记法：把这三个概念翻译成“我站在哪”“我能往哪走”“我一开始站哪”。

先说“我站在哪”——状态。说白了就是dp数组的下标代表着什么含义。在斐波那契里，dp[i]表示“斐波那契数列的第i项值”。在爬楼梯问题里，dp[i]表示“爬到第i阶一共有多少种方法”。状态定义是整个动态规划最关键的一步，定义得好，转移方程顺手就来；定义得烂，后面寸步难行。我这个系列的原则是“状态必须能回答一个具体的问题”，而不是模模糊糊地说“dp[i]是一个值”。怎么检验状态定义够不够清楚？你闭上眼，能把这个状态翻译成一句人话，就算过关。

再说“我能往哪走”——状态转移方程。它的本质是一个递推关系，告诉你“当前状态是怎么由更小的状态算出来的”。我当初理解错的一点是：总以为转移方程是从题目里“看出来”的，其实不是，它是从你的状态定义和问题要求里“推出来”的。以爬楼梯为例，如果我知道“到第i-1阶的方法数”和“到第i-2阶的方法数”，那么到第i阶，就是最后一步从第i-1阶跨上来，或者从第i-2阶跨上来，两条路相加。转移方程不是灵感，是逻辑推理的结果。

最后说“我一开始站哪”——初始化和边界条件。初始化就是给dp数组最开头的那几个位置赋予一个明确值，这个值通常不能由转移方程算出来，必须靠常识和题目语义确定。很多人的困惑来了：为什么斐波那契要特别设置dp[0]=0、dp[1]=1？因为dp[0]和dp[1]没有“更小的前驱状态”，公式dp[i]=dp[i-1]+dp[i-2]在 i=0 或 i=1 时是取不到合法参数的，所以必须手动给值。

我还踩过一个典型的坑：硬背“dp[0]=0”。后来做到另外一道题，发现必须dp[0]=1才正确，因为那个dp[0]表示“空序列有1种组合方式”。所以不要背初始化，要从意义上理解它。为了帮自己彻底理清，我做了下面这个对照表：

我试图用这三问来帮助自己记忆。你以后做任何一道动态规划题，先问自己：我站在哪？我能往哪走？我一开始站哪？这三问只要答得出来，代码就是水到渠成的事情。答不出来的话，说明你还没理解题目本身，应该先回去画图、举例子，而不是硬憋代码。

另外，这三问还有一个隐藏的第四问：我按什么顺序走？也就是遍历顺序。这个后续讲到0-1背包时才显得至关重要，因为遍历顺序直接决定了结果的正确性。

4. 爬楼梯：从零开始推状态方程，再顺手做一次滚动优化

为了不让你觉得我光说不练，现在找一个可以完整复活的入门题目。日常刷题社区里应该都见过这道题：假设你正在爬楼梯，每次只能迈1级或者2级台阶，要爬上n级台阶，一共有多少种不同的走法？我第一次看到这道题时也是一头雾水，想的是“这不就是用排列组合吗”。用动态规划来看，它的逻辑比排列组合直观得多。

先套用三问。状态定义：dp[i]表示“爬到第i级台阶的不同走法数量”。转移方程：要爬到第i级，最后一步只有两种可能，要么从第i-1级迈1级上来，要么从第i-2级迈2级上来，所以dp[i]=dp[i-1]+dp[i-2]。初始化：第一级台阶只有一种走法（直接迈1级），所以dp[1]=1；第二级台阶可以1+1或直接2，所以dp[2]=2。从i=3开始，用循环递推，答案就是dp[n]。

写成代码，大概是这样的：

def climb_stairs(n: int) -> int: 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]

这里有一个值得细想的细节：为什么要从3开始循环？因为dp[1]和dp[2]是我们手动初始化的。如果你非要写成从1开始也行，但那样要么数组越界，要么得在循环里加一堆防越界的判断，代码明显变丑。养成好习惯：手动初始化前面若干个必要状态，然后从第一个“可以由转移方程推出”的下标开始循环。

等你写完这个基础版本，可能就会想：需要一整个数组把所有中间结果都存下来吗？答案是：不需要。因为你推dp[i]的时候，只用到了dp[i-1]和dp[i-2]，更早的数据根本不会再被用到。这就像你走路的时候，不需要记住自己三天前在哪个台阶，只要知道上一级台阶和上上一级台阶就够了。这种把dp数组压缩成几个变量的技巧，叫“滚动数组”或者“状态压缩”。

压缩后的代码长这样：

def climb_stairs(n: int) -> int: if n <= 2: return n prev, curr = 1, 2 for _ in range(3, n + 1): prev, curr = curr, prev + curr return curr

很多人看到这个写法会问：prev, curr = curr, prev + curr这一行到底怎么执行？在Python里，右边的值会先用旧值计算完，再统一赋值给左边。所以它等于：

temp = curr curr = prev + curr prev = temp

我建议你初学阶段别直接用压缩写法，先老老实实写一整个dp数组，哪怕多占点空间，也逼自己把dp[i]的语义想明白。等数组版彻底通了，再压缩。压缩的好处不仅是省空间，更能强迫你思考“哪些状态是真正需要保留的”，这对后面理解背包问题的状态压缩很有帮助。

爬楼梯这道题，如果你已经会了，还可以顺手试试它的两个变体，检验一下自己是不是真理解了：第一个变体是“每次可以走1级、2级或3级”，问方法数；第二个变体是“有的平台有体力花费，需要算最小体力花费”。这两个变体不会改变整体思考方式，但会逼你重新审视状态定义和转移方程。我只能说，如果第一个变体你还想半天，大概率是在生搬硬套原来的dp[i]=dp[i-1]+dp[i-2]，而不是真正理解了“最后一步有哪些走法，就把哪些子状态加进来”。

5. 0-1背包：为什么二维转一维时必须倒着遍历容量

爬楼梯解决了一半的问题，让你理解“状态怎么一层层推”。但动态规划里还有一些问题，每一步都需要做“选择”，纠结露骨。经典的0-1背包问题就是这种类型。问题长这样：有一个能承重W的行李包，有n件物品，每件物品有自己的重量w[i]和价值v[i]，问如何选取物品，使包内总价值最大。每件物品要么装一下，要么不装，不能切割，不能装一半，所以叫0-1背包。

我第一次看到这个问题，第一反应是“按价值/重量比值排序，从高到低装”。这个贪心思路听起来很有道理，但实际上是错的，因为物品不能分割，把高价值高重量的物品装上，可能导致包内剩余空间太小，反而装不下几件轻但是性价比高的物品。贪心在局部看起来是对的，但不能保证全局最优。动态规划就是用来做这种“组合决策”的。

先定状态。这里有两个维度：处理到第几件物品、当前用了多少容量。所以状态是二维的，用dp[i][j]表示“在前i件物品中选，且包内容量恰好为j（或者说不超过j）时，能获得的最大总价值”。这个状态定义的合理性在于：我们不可能只用一个一维下标同时表达“考虑了哪些物品”和“用了多少容量”这两个信息，所以必须开二维数组。

再推转移方程。对第i件物品，做决策时只有两种可能。第一种：不选它，那dp[i][j]=dp[i-1][j]，意思是我只看前i-1件物品方案。第二种：选它，但前提是包容量足够，即j >= w[i]，这时dp[i][j]=dp[i-1][j-w[i]]+v[i]。注意j-w[i]是给这件物品腾出空间之后的剩余容量，我们要用的是“在前i-1件物品里用j-w[i]容量能得到的最大价值”，这体现了“之前的选择结果可以被引用”的动态规划核心思想。

把两者取一个最大值，就得到完整的转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) // 仅当 j >= w[i] 时

初始化行和列：容量为0时，任何物品都放不下，所以dp[i][0]=0；一件物品都不考虑时，dp[0][j]=0。代码大概长这样：

def knapsack_01(weights: list, values: list, capacity: int) -> int: n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): wt = weights[i - 1] val = values[i - 1] for j in range(1, capacity + 1): if j >= wt: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wt] + val) else: dp[i][j] = dp[i - 1][j] return dp[n][capacity]

注意一个小坑：weights和values的下标我用了i - 1，因为dp数组第0行表示“不考虑任何物品”，物品编号从1开始对应到原始列表下标0。这是很多人写错的地方，我再强调一次：dp数组的行数比物品数多1，列数比容量大1，纯粹是为了让“前0件”“容量0”这些初始状态有地方放。

二维版本虽然好懂，但空间复杂度是O(n*capacity)，在资源受限的情况下不够优雅。经典优化方法是把它压成一维数组：dp[j]表示“容量为j时能装的最大价值”。代码改成：

def knapsack_01(weights: list, values: list, capacity: int) -> int: dp = [0] * (capacity + 1) for wt, val in zip(weights, values): for j in range(capacity, wt - 1, -1): dp[j] = max(dp[j], dp[j - wt] + val) return dp[capacity]

这里有个关键的、很多新手都会踩的坑：一维优化后，内层循环容量j必须从大到小遍历，也就是从capacity往wt的方向遍历。为什么？因为一维数组里只保留“当前层”的dp值，而当我们更新dp[j]时需要用到dp[j-wt]的旧值，这个旧值代表“只考虑前i-1件物品”时的结果。如果j从小到大遍历，那么dp[j-wt]可能已经在当前这轮被更新过了，覆盖成“已经考虑完第i件物品”的结果，这样就会导致同一件物品被重复使用，从而退化成完全背包问题，而不是0-1背包。

我打个比方你就能懂：假设你面前只有一张白纸，每一行只能写最新结果。你想用原来的第4行的数字去更新第6行，但如果你先把第6行正着写了，再回去找第4行，发现它已经被你写成了一个新值。要避免这种串味，只能从纸的下面往上写，这样你用的永远是还没被动过的旧数据。这就是“倒序遍历”最直白的解释了。

我在第20天做这道题时，还特意做了一个小实验来验证自己没白学：用二维版跑一遍答案，再注释掉一维版，对比两者输出是否一致。如果在容量够大的背包里塞几个数据，你会发现结果一模一样，但一维版省下了好几MB内存。这种动手对拍的习惯，我强烈建议你养成，它能帮你发现很多理解的盲区。

6. 判断一道题能不能用动态规划：两个信号和我的四问检查表

你可能会问：“爬楼梯和0-1背包都会了，那我怎么知道一道新题该不该用动态规划？”这个问题问得好，在第20天这个节点，我觉得比再刷十道题更有价值。动态规划不是万能药，如果一道题用了暴力DFS也能轻松过，你硬上动态规划属于过度设计。我的经验是，新手先看两个信号：重叠子问题和最优子结构。

“重叠子问题”的信号是：暴力递归时，同样的参数组合会被重复计算。你可以在递归函数里加一个计数器，看看某些参数出现了多少次。比如斐波那契的递归中，n=3这个子问题被反复计算了很多次，这就是重叠子问题。没有重叠子问题，动态规划的缓存就完全白搭，因为每个子问题只算一次，缓存没有任何复用机会。这种情况下，通常直接搜索或分治就够了。

“最优子结构”的信号是：一个问题的最优解，可以由子问题的最优解组合推导出来。这里最容易犯的毛病是把它跟“子问题都有最优解”混淆。所谓“最优子结构”强调的是：我算出子问题的最优解之后，可以直接拿来拼出父问题的最优解，不需要回头再研究子问题的其他解。爬楼梯里，全局方法数就是两个子方法数相加；背包问题里，装第i件物品的最优价值是“用剩余容量装前i-1件的最优价值”加本身价值。明显的反例是最短路径问题里，如果图里存在负权边，局部最短路径组合起来就不一定是全局最短路径，这就破坏了最优子结构。

如果这道题两个信号都出现了，那就可以用我积累的四问检查表来落地：

1. 状态怎么定义？答出dp[i]或dp[i][j]代表什么，并能翻译成一句人话。
2. 转移方程是什么？当前状态由哪些更小的状态推出，每一步有哪些选择？
3. 初始化怎么定？哪些状态不能由转移方程直接得到，要靠常识赋值？
4. 遍历顺序怎么走？是从小到大还是从大到小，是一层还是两层循环？

这个检查表看起来简单，但实际做题时经常出问题。我见过很多新手（也包括我自己初期）在一道题上卡住，不是不会写转移方程，而是状态定错了。状态定成“以i结尾的最大子段和”和定成“前i个元素的最大子段和”，整个思路完全不同。前者通常更容易和“当前位置必须选”绑定，后者需要考虑“选或不选当前元素”两个分支。所以我把第一问放在最前面，因为它几乎是成败的一半。

为了更直观地展示四问的作用，我列一个自查表：

如果你能拿着这个表，把每个经典题目都套一遍，慢慢你会发现一种“题感”——看到“有多少种方案”“最大最小价值”“能不能达到某个目标”这类问题，第一反应就是动态规划。当然也有例外，有些“方案总数”题可以用组合数学，有些“最值”题可以用贪心，但那都是后话了，从动态规划入手更稳妥，不容易漏解。

我在第20天给自己留的另一个小任务是：拿之前做过的DFS回溯题来对比。比如走迷宫找路径和统计方案数，走迷宫只需要找到任意一条路径，DFS多半够了；但统计方案数并且允许重复经过某些格子时，经常就需要动态规划。这个认知，算是今天最大的收获之一，因为它把“搜索”和“动态规划”在我脑子里连成了一串。

我个人在连续打卡20天之后最大的体会是：算法学习从来不是比谁聪明，而是比谁更能把大问题拆小。动态规划所有看似玄学的部分，拆到最后都只是“别重复劳动，把中间结果记下来”。第20天结束，我不认为自己已经精通动态规划，但我拿到了一个能自主推演的思考框架。如果你也想在这个系列里走到这儿，我的建议很简单：电脑前摊开草稿纸，把今天提到的三道题——斐波那契、爬楼梯、0-1背包——全部从暴力递归开始推导一遍，每一步都亲手写。等你写完，你会发现自己已经跨过了那道“看答案秒懂、自己做就卡壳”的坎。