企业官网建设流程全解析

打卡到Day40那天，我真正感受到了什么叫"算法训练营的分水岭"。前一天的贪心算法题，我还能靠"局部最优推全局最优"拍脑袋蒙对几道；结果早上一打开题目列表，看着"斐波那契数"这四字，我还松了口气——这题多熟啊。然后鼠标往下滑，"爬楼梯""不同路径"，我盯着第一道题半天没动手：不是不会写递归，而是隐约意识到，代码随想录这一天的题，要把我之前学过的几乎所有套路重新洗牌。这一篇就算是我自己的Day40复盘，说说三道入门题怎么从暴力一步步走到动态规划，以及DP五部曲到底该怎么用。如果你也正好在训练营中段摸爬滚打，希望这份记录能给你一点参照。

1. Day40的题目清单与训练营进度坐标

先交代一下进度背景。Day40放在整个训练营里的位置挺特殊的：数组、链表、哈希表、字符串、二叉树、回溯、贪心这些都过了一遍，递归思维刚被二叉树和回溯题练得有点感觉，贪心又让你开始习惯"拍脑袋猜局部最优"。就在你以为自己终于开始"会做题"的时候，动态规划突然出现，把一切都推到重来。

我这里说的Day40，对应的是动态规划基础篇，当天题单大概是下面这几道：

不同期次的训练营安排会有细微差异，但入门题基本就是这个范围。很多人这一天会开始弃坑，原因也很真实：前39天你刚觉得"二叉树不过如此，回溯也就套模板"，结果拿到爬楼梯这道题，连dp数组该是一维还是二维都要想半天。这种挫败感不是题目难，而是你之前建立的解题直觉在DP这里不生效了。

我自己的体会是，Day40真正要解决的事有两件：第一件，理解"重叠子问题"和"状态转移"这两个词到底在说什么；第二件，把代码随想录反复提的DP五部曲落实到具体题目里，而不是当成口号背过去。这两件事做不到，后面01背包、完全背包、打家劫舍、股票问题全是空中楼阁。

2. 贪心算法为什么在动态规划面前"失灵"了

在聊DP之前，必须先聊聊贪心。因为Day39和Day40之间那道看不见的裂缝，就是贪心与DP的分歧点。

贪心算法的核心思路是"局部最优推导全局最优"。做分发饼干那道题的时候，你只需要每次把当前最小的饼干喂给当前胃口最小的孩子，不需要回头看之前的选择。为什么不用回头看？因为这道题的局部决策不会影响后面可用的选项，也不存在"这次选了A会让以后少一个机会"的后悔场景。

但爬楼梯这道题一出来，情况就完全变了。题目问的不是"怎么走最优"，而是"一共有多少种走法"。你站在第3级楼梯上，既可能是从第2级跨了一步上来，也可能是从第1级跨了两步上来。这两种走法都需要统计，没有哪个比另一个更优——目标函数从"求最优值"变成了"求方案总数"。贪心算法在这种场景下直接没有用武之地，因为根本没有一个"局部最优"可以贪。

那递归行不行？行，但代价非常大。爬楼梯的朴素递归树会指数级膨胀，n=45的时候在你的电脑上已经能明显卡顿。问题出在重叠子问题上：算f(10)要算f(9)和f(8)，算f(9)又要把f(8)和f(7)重新算一遍，f(8)被重复计算了两次，f(7)被重复计算了三次——越往底层，重复计算越离谱。

动态规划做的事情，说白了就是把这个"重复计算"干掉：从最底层开始，把每一个子问题的答案记下来，后续需要的时候直接查表，而不是重新递归。你可以把它理解成一个记账的过程。

贪心是走一步看一步，兜里揣一张当期最优的纸条；动态规划是你有一本总账，每一步都翻以前的账目，算完当期再记一笔新的。

这两个思维模式切换起来很别扭。我在Day39做题时习惯了"先猜一个贪心策略，然后跑两个用例验证"，到了Day40发现这招完全不灵了。后来才明白，贪心和DP不是简单的前后关系，而是一道分岔口：当你发现一个问题的求解依赖多个更小的子问题，并且这些子问题反复出现时，你就该从贪心的路口拐进DP这条路了。

3. 三道入门题从暴力到DP的完整演进

这一章是当天的重头戏。我没有直接看题解，而是把每道题都先从最原始的暴力写法开始推，再一步步优化到DP。真的强烈建议你也这么走一遍，直接背DP模板其实没意义。

3.1 斐波那契数：先写递归，再懂DP为什么快

斐波那契数这题谁都见过，但训练营的难点在于逼你用动态规划的角度重新看它。题目本身一句话：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)。

大多数人的第一反应是写递归：

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

这代码干净、优雅，但n=40的时候就开始吃力，n=100基本算不出来。问题就出在那棵指数级膨胀的递归树上——你可以自己在纸上画一下n=5的递归调用，会发现fib(3)被算了两次，fib(2)被算了三次。每个结点都在重复劳动，复杂度是O(2^n)。

第一个优化是加备忘录，也就是记忆化搜索：

def fib(n): memo = {} def helper(k): if k <= 1: return k if k in memo: return memo[k] memo[k] = helper(k - 1) + helper(k - 2) return memo[k] return helper(n)

加了一个memo字典，复杂度立刻降到O(n)。但这还不是标准的动态规划写法——它依然是"从上往下递归"，只不过把重复计算结果缓存了。真正的DP思维是把这个过程反过来，从底部开始填表：

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

你看，递推公式本身没变，变的只是遍历方向。自顶向下和自底向上是同一个关系式的两种展开方式，但后者不需要递归栈，也不会重复计算。

这题还能做空间优化。你会发现dp[i]只用到了前两个值，根本不需要整个数组：

def fib(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b

这就叫滚动数组。三种写法的复杂度对比如下：

这道题唯一的坑在于不要把n看成下标错位。n=0时直接返回0，dp[1]才是1，很多人一上来先初始化dp[0]=1，结果整个数列整体平移一位，最后全部报错。

3.2 爬楼梯：从题目里"挖出"递推公式

爬楼梯这题是Day40真正的灵魂。题目看似比斐波那契难了一个档次，但推到最后发现，它就是披着应用题外衣的斐波那契。

题目描述很简单：你站在第1阶，每次可以爬1阶或2阶，问到n阶一共有多少种走法。

关键是抓住最后一步。你要到第i阶，只有两种可能：从第i-1阶迈一步上来，或者从第i-2阶迈两步上来。所以到第i阶的方案数，就是这两种路径的方案数之和：

dp[i] = dp[i - 1] + dp[i - 2]

这行式子一推出来，后面的代码跟斐波那契一模一样：

def climbStairs(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]

这里有个细节值得说一下：为什么dp[2]=2而不是3？因为题目说"每次可以爬1阶或2阶"，爬到第2阶只有两条路：一次跨2阶，或者连续跨两次1阶。有些人会手滑把它算成3，多半是把"爬3阶的走法"提前脑补进来了。

另一个经典争议是dp[0]到底该是几。如果你直接用dp[0]=1来让公式统一，确实方便，但初学者很容易搞不清dp[0]代表什么。我更推荐直接初始化dp[1]和dp[2]，绕开这个概念的坑。后面学到更复杂的题目时，你再回来体会dp[0]的"无意义但有价值"。

同样可以用滚动数组压缩空间：

def climbStairs(n): if n <= 2: return n prev, cur = 1, 2 for _ in range(3, n + 1): prev, cur = cur, prev + cur return cur

我那天在这个滚动数组上踩了个小坑：把prev和cur的赋值顺序写反了，结果输出一直比正确答案小1。后来才反应过来，这句赋值右边的prev是上一轮的cur，必须同时更新，不能拆成两个单独的赋值语句。

3.3 不同路径：一维数组的压缩技巧

不同路径这道题把DP从一维拉到了二维，是Day40真正拉开差距的一道题。题目说：一个m行n列的网格，机器人从左上角出发，每次只能向右或向下走，问到达右下角有多少条不同路径。

一开始我想用排列组合直接算：一共要向右走n-1步、向下走m-1步，总步数m+n-2，在其中挑m-1个位置向下走，答案就是C(m+n-2, m-1)。这方法能算，但训练营的用意显然不是考组合数学，而是让你理解二维状态。

DP的视角是这样的：dp[i][j]表示从起点走到网格第i行第j列有多少条路径。由于机器人只能向右或向下，那么到达(i,j)只能来自(i-1,j)或(i,j-1)，所以：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

边界条件也很直观：第一行的任意格子，都只能一路向右走，所以只有1条路；第一列的任意格子，只能一路向下，也只有1条路。初始化时把这些格子都设为1：

def uniquePaths(m, n): dp = [[1] * n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[m - 1][n - 1]

注意Python里初始化二维数组要用[[1] * n for _ in range(m)]，不要写[[1] * n] * m。后者会让每一行共享同一个列表对象，改一行全部跟着变。

二维DP的空间还能继续压。观察递推公式可以发现，算第i行时只需要第i-1行和当前行的左边格子，所以完全可以用一个长度为n的一维数组滚动：

def uniquePaths(m, n): dp = [1] * n for i in range(1, m): for j in range(1, n): dp[j] = dp[j] + dp[j - 1] return dp[n - 1]

这里最难理解的就是那句dp[j] = dp[j] + dp[j - 1]。第一次看到的人都会懵：右边两个dp[j]到底谁是谁？我的理解方式是这样的：内层循环在更新第i行，此时dp[j]还保留着上一行第j列的结果，它代表dp[i-1][j]；而dp[j-1]在本次循环里已经被更新成当前行第j-1列的结果了，所以它是dp[i][j-1]。两者相加，正好就是新的dp[i][j]。

这行代码在纸上跑一遍比看十遍解释都管用。我建议你拿m=3、n=3手动推一轮：第一轮循环结束后数组是[1,2,3]，第二轮再走一遍就变成[1,3,6]，最后的6就是答案。

三种解法的效率对比：

做题时别急着追求一维滚动，先二维想清楚，再压缩。一维滚动是优化，不是第一优先级。

4. 被代码随想录反复强调的DP五部曲，每一步都在解决什么

Day40真正的收获不是AC了三道题，而是把DP五部曲彻底内化了。代码随想录里反复强调这个套路，我一开始觉得啰嗦，直到自己独立做变体题时卡壳，才服气。

这五步是：确定dp数组含义、确定递推公式、初始化dp数组、确定遍历顺序、举例推导dp数组。每走一步都有它存在的理由。

第一步，确定dp数组以及下标的含义。这一步最容易被跳过，但恰恰是最关键的。比如爬楼梯，dp[i]的含义是"爬到第i阶的方法总数"；不同路径，dp[i][j]的含义是"到达第(i,j)格的路径数"。含义不同，后面所有推导都会跟着变。我见过有人把dp[i]理解成"在第i阶还能走的步数"，最后公式怎么推都不对。这个错误不是计算问题，是状态定义错了。

第二步，确定递推公式。递推公式不是背出来的，是分析"最后一步怎么来的"推出来的。爬楼梯的最后一步要么跨1阶要么跨2阶；不同路径的最后一步要么从上面来要么从左边来。这种"最后一步分析"是DP题最通用的思考方法。注意在推导公式时，先不要想初始化，很多人会把初始化和递推混在一起想，结果越搞越乱。

第三步，dp数组如何初始化。初始化的依据是第一步里定义的含义。斐波那契里dp[0]=0、dp[1]=1，是因为定义如此；爬楼梯里dp[1]=1、dp[2]=2，是由题目条件推出；不同路径里第一行第一列为1，是因为这些格子的路径只有一条。初始化的核心原则是：给递推公式提供正确的起点，而不是随便填。

第四步，确定遍历顺序。大多数入门题都是从前往后遍历，因为dp[i]依赖更小的下标。但不同路径这种二维题，你得保证计算dp[i][j]时，dp[i-1][j]和dp[i][j-1]都已经算完。所以外层从上到下、内层从左到右。到了后面的背包问题，遍历顺序会成为最大的考点，但Day40你只需要建立这个意识：遍历顺序取决于状态依赖的方向。

第五步，举例推导dp数组。这是我以前从来不做的一步，也是Day40之后我改掉坏习惯的关键。拿n=5跑一遍爬楼梯：dp[1]=1，dp[2]=2，dp[3]=3，dp[4]=5，dp[5]=8。如果结果是8，说明逻辑没问题；如果跑出别的数，大概率是初始化或公式错了。手动推导的过程就像在给代码写"冒烟测试"。

那天我做最小花费爬楼梯时，就是靠第五步救命。题目要求从第0阶或第1阶开始，每次爬1或2阶，每个台阶有对应体力花费，求到楼顶的最小花费。我一开始把dp[0]初始化为cost[0]，导致结果偏小。后来手动推导dp数组才发现，dp[i]应该表示"到达第i阶并支付完该阶费用的最小花费"，从第0和第1阶开始时不支付任何费用，所以dp[0]=dp[1]=0才对。这种错误，不手动推两遍数组根本发现不了。

初学者最常见的几个问题和修法，我整理了一下：

五部曲看起来很机械，但它保证了你面对任何DP题都有一个稳定的处理顺序。尤其是Day40这种入门阶段，靠着这个顺序，你至少能写出一个结构正确的错误答案，而不是坐在那里发呆。

5. Day40之后的收尾动作：错题整理与心态调整

最后说说当天做完题之后我做了什么，以及那些题解上不会写的东西。

首先是错题整理。我给自己定了一条规矩：每道DP题必须在本地按五部曲写一遍注释，哪怕AC了也要写。格式很简单：dp[i]代表什么、递推公式怎么来的、初始化为什么是这些值、遍历顺序为什么这样。写注释的过程能暴露很多"自以为懂了"的盲区。比如不同路径那道题，我AC的时候用的是二维DP，但写注释时发现自己根本说不清为什么边界是1，这才老老实实回去补了滑动数组的推导。

其次是节奏问题。Day40之后我明显感觉到，一天刷三道新题 + 复习两道旧题已经是上限。DP和前面的章节不一样，它需要你反复咀嚼。贪心题你AC了就是AC了，DP题你AC了不代表你掌握了——换一个初始条件、改一个遍历方向，你可能立刻又不会了。我在那天把做过的三道题换了各种变体去测：爬楼梯改成"可以爬1、2、3阶"，不同路径改成"某几个格子有障碍"，每次改动都暴露出新的理解漏洞。

心态方面，我能给的唯一建议是：怕做不出来很正常。我自己前39天建立了"好像什么题都见过"的虚假信心，Day40被爬楼梯一道题就戳破了。但戳破是好事，动态规划本来就是训练营中后期真正的分水岭，你在这里卡住，说明你在认真用脑，而不是在背模板。

一个非常有效的小技巧：给自己留一个"顿悟记录本"。我第一次真正理解"为什么斐波那契和爬楼梯是同一个递推"时，在旁边写了一句"原来状态转移就是把最后一步的两种可能性相加"。后来学到完全背包的时候回看这句话，又冒出了新的理解。这种自己写下的顿悟，比任何教程的干货都更适合你。

Day40打卡结束那天，我在便签上写了一句话：动态规划不是一种解法，而是一套记账的思维方式。后来学到01背包、完全背包，我也一直用三步问自己：这个状态的含义是什么、它从哪些状态转移过来、我先填哪里才不会用到还没算出的值。如果你今天正好卡在训练营的第40天，别急着往下赶进度，把斐波那契、爬楼梯、不同路径这三道题从头到尾推一遍，再来一篇五部曲注释，你回头看贪心题单的眼神都会不一样。