企业官网建设流程全解析

从一道最少硬币题开始，聊聊动态规划到底在干什么

今天是我算法学习打卡的第44天，前阵子一直在跟贪心、回溯、搜索这些“偏策略”的算法打交道，今天正式进入动态规划这个大名鼎鼎的领域。

说实话，动态规划这四个字，我在网上看了不下十遍——有人叫它DP，有人喊它“状态转移大法”，还有人直接说“想不明白就背模板”。但在真正动手做了一天题之后，我的感受是：动态规划不是一种具体的算法，而是一种思考问题的方式。今天这天的学习路线是：从最少硬币问题切入，理解“状态”“转移”“最优子结构”这几个核心概念，然后上手01背包，最后把动态规划和贪心、递归做了个对比总结。

这篇文章不是我抄什么题解整理出来的，而是把我从“看到题目一脸懵”到“能自己写出状态转移方程”的全过程，包括中间的思路卡壳、踩坑和调试记录，完整记录下来。如果恰好你也卡在动态规划入门这个坎上，这篇内容应该能帮你在思路层面捅破那层窗户纸。

1. 动态规划到底是个啥？先忘掉“状态转移方程”这六个字

1.1 从暴力递归说起：为什么重叠子问题这么关键

很多人第一次接触动态规划，上来就甩给你一个dp数组、一个状态转移方程，然后让你背。这其实是完全错误的学习路径。

我自己的理解方式是倒退回去，先看一个最简单的例子：计算斐波那契数列的第n项。教科书会告诉你F(n)=F(n-1)+F(n-2)，这本身就是一个递归过程。但如果你画一下递归树，你会发现F(5)要算F(4)和F(3)，而F(4)又要算F(3)和F(2)——同一个子问题被反复计算了无数遍。这种“大问题拆成小问题，小问题又互相重叠”的结构，就是动态规划能起作用的前提。

所以学动态规划的第一步，是识别一道题能不能用动态规划来解。判断标准有两条：一是有没有重叠子问题，二是有没有最优子结构。什么叫最优子结构？简单说，就是整个问题的最优解，可以由子问题的最优解推导出来，而不是需要另起炉灶重新计算。

我记得本科时有一次面试，面试官问我的问题是：“动态规划和分治算法的区别是什么？”我当时答得磕磕绊绊。现在回头看，答案其实很清晰——分治算法（比如归并排序）把问题拆成互不相交的子问题，分别解决后合并；而动态规划面对的子问题之间是有交集的，既然是交集，就可以用一张表把这些中间结果记录下来，避免重复计算。

1.2 状态、转移、边界：入门动态规划的三个核心要素

在真正写代码之前，我建议你先建立一套自己的分析框架。我按照网上的教程加上自己的调试经验，总结出一套万能的“三步走”：

第一步，定义状态。状态就是你用什么东西来描述当前所处的情况。比如最少硬币问题里，dp[i]可以定义为“凑出金额i所需的最少硬币数”，这里i就是状态变量。

第二步，写状态转移方程。也就是思考：当前这个状态，是怎么从之前的状态变过来的？还是以硬币问题为例，dp[i]应该等于dp[i - coin] + 1对每个面额的硬币取最小值。这一步是整个动态规划的核心，也是最难的部分，后面我会专门展开讲。

第三步，确定初始化和遍历顺序。边界条件决定了递归或循环的起点，遍历顺序则决定了你在计算某个状态时，它依赖的状态是否已经被算出来了。

这三个要素，正好对应了动态规划题解里最常见的三段式代码结构——初始化dp数组、循环计算、返回答案。初学者一开始不用急着理解所有细节，先照着这个框架去套题，套多了自然就有感觉了。

1.3 记忆化搜索和自底向上：动态规划的两种打开方式

我第一天学动态规划，发现同一个题解里，有的人写递归+备忘录，有的人写for循环数组，结果还是一样的。这里需要搞明白，动态规划有两条技术路线：自顶向下（记忆化搜索）和自底向上（表格递推）。

自顶向下比较好理解，就是写递归函数，但是用一个memo数组把算过的结果存下来，下次直接用。这种方式符合人脑的直觉，代码也容易写，缺点是递归有栈溢出风险，尤其是数据量大的时候。

自底向上则是反过来，从最小的子问题开始，用循环一点点推到目标问题。代码性能稳定，但思维方式和递归不同，需要你先想清楚所有可能的状态，然后按顺序填表。

很多入门教程只讲自底向上这一种，让人误以为动态规划必须用数组加循环。实际上，我在做最少硬币问题的时候，就是先写了递归版本来验证状态转移方程是否正确，再改成循环版本去提交，这样做正确率会高很多。

2. 经典入门题实战：最少硬币问题全解析

2.1 题目描述和第一直觉（一个典型的错误思路）

先看今天的第一个例子，可以说是动态规划界的“hello world”——最少硬币问题。题目很简单：给定一堆不同面额的硬币（比如1元、3元、5元），以及一个目标金额（比如11元），问你凑出这个金额最少需要多少枚硬币，如果凑不出来就返回-1。

我第一次拿到这个题，第一反应是——这不就是贪心吗？先把大面额硬币往死里用，不够了再用小面额补齐。比如11元，先用5元硬币，用两个还剩1元，再用一个1元硬币，总共3枚，完美。

在硬币面额是1、3、5的情况下，贪心确实能凑出正确结果。但问题是，如果硬币面额变成2、5、7，目标金额是11呢？贪心会先用两枚5元，剩1元发现凑不出来，于是宣告无解。可实际上，5+2+2+2等于11，需要4枚硬币，是有解的。所以贪心算法依赖硬币面额的特定性质，而动态规划不需要这种依赖，它通过穷举所有组合来保证找到最优解。这个反例，就是我开始理解“动态规划为什么比贪心更通用”的起点。

2.2 从递归到记忆化，再到递推的完整推导

那动态规划怎么做？我还是按照上一节的三步走来推导。

第一步，定义状态。我用dp[i]表示“凑出金额i需要的最少硬币数”。如果i等于0，那当然一枚硬币都不用，所以dp[0]=0。

第二步，写状态转移方程。凑出金额i，最后一步一定是放了一枚面额为c的硬币，那么之前的金额是i-c，对应的最少硬币数就是dp[i-c]，再加1就是当前这枚。对所有硬币面额遍历，取最小值就行：

dp[i] = min(dp[i - c] + 1) 对所有满足 c ≤ i 的硬币面额c

第三步，确定初始化和遍历顺序。dp[0]=0，其他值先初始化为一个大数（比如inf），然后从i=1一直算到i=amount。

按照这个思路，我写出来的核心代码长这样：

def coinChange(coins, amount): # 初始化dp数组，长度为amount+1，全部填充一个大数 dp = [float('inf')] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for c in coins: if i >= c: dp[i] = min(dp[i], dp[i - c] + 1) return dp[amount] if dp[amount] != float('inf') else -1

这里有个细节我想多说两句：初始化时为什么用inf而不是-1？因为dp[i]的语义是“凑出金额i的最少硬币数”，在还没有计算出结果之前，它处于“未知”状态，而“未知”对于min操作来说，应该被当作正无穷来处理，这样任何有效值都能覆盖它。如果用-1初始化，min的时候就会永远取到-1，逻辑就全错了。

2.3 复杂度分析和为什么“最少硬币数”能拆成子问题

这个代码的时间复杂度是O(amount * len(coins))，空间复杂度是O(amount)。注意，amount可以是几千甚至几万，这个复杂度是完全能接受的。

但代码能跑对，不代表你理解了为什么能这么拆。我那天想了很久，最终用一个生活化的类比说服了自己：你要从地面爬到第100级台阶，一次可以跨1级或者2级，问最少跨几次。你不用从第0级开始模拟每一级怎么踩，你只需要知道：爬到第100级的最后一步，要么是从第99级跨1级上来的，要么是从第98级跨2级上来的。所以f(100) = min(f(99), f(98)) + 1。

硬币问题同理。凑出11元的最后一步，要么放了一枚5元（前面凑6元），要么放了一枚3元（前面凑8元），要么放了一枚1元（前面凑10元），所以dp[11] = min(dp[6], dp[8], dp[10]) + 1。这就是把大问题拆成小问题的本质——永远只关注最后一步发生了什么。想通了这一点，之后遇到再复杂的动态规划题，我都能快速找到切入点。

3. 进阶必考题：01背包问题的思路拆解

3.1 从“选还是不选”的角度理解背包问题

最少硬币问题算是热身，今天真正让我卡了快两个小时的是01背包问题。题目描述很朴素：有一个容量为W的背包，有n件物品，每件物品有重量w[i]和价值v[i]，问你最多能装下多大价值的东西。

为什么叫“01”？因为每件物品只有两种选择：装进去（1）或者不装（0），不能装一半，也没有“无限件”。这个问题看似和硬币问题很像，但有个关键区别：硬币问题不限制硬币数量，而背包问题的每件物品只有一件。所以硬币的dp[i]循环一遍就行，而背包的循环顺序有讲究，一不留神就会把同一件物品用无数次，变成完全背包问题。

我第一次写背包代码，就直接套了硬币的模板，结果答案大得离谱。后来查了半天才知道，01背包需要倒序遍历容量，目的就是为了保证每件物品只被使用一次。

3.2 二维dp和一维滚动数组的演变过程

先看最基础的二维dp版本。定义dp[i][j]为“考虑前i件物品，背包容量为j时能装下的最大价值”。那么对于第i件物品，有两种情况：

• 不装：dp[i][j] = dp[i-1][j]
• 装（前提是j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]

两者取最大值。伪代码是：

for i in range(1, n + 1): for j in range(W + 1): if j < w[i]: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

这个版本空间复杂度是O(n*W)，如果n和W都到几千，内存就爆了。所以需要优化成滚动数组，也就是只保留一维，每次更新时覆盖旧值。但这里有一个最大的坑：j必须从大到小遍历。

dp = [0] * (W + 1) for i in range(1, n + 1): for j in range(W, w[i] - 1, -1): dp[j] = max(dp[j], dp[j - w[i]] + v[i])

我一开始完全不能理解为什么要倒着来，后来自己手算了几个值才明白：正序遍历时，dp[j-w[i]]可能已经在当前这轮循环中被更新过了，那它代表的就是“已经装了当前物品”的状态，相当于同一件物品被重复装了好几次。而倒序遍历时，dp[j-w[i]]还是上一轮的值，也就是还没装当前物品的旧状态，这样才符合01背包“每件最多一次”的约束。

3.3 一个实例演练：容量10的背包，四件物品怎么装

光说理论容易飘，我那天用一个具体例子手算了一遍才算彻底放心。假设背包容量W=10，四件物品如下：

按一维dp倒序遍历，第一轮处理物品1（w=2,v=3），dp[10到2]会变成3。第二轮处理物品2（w=3,v=4），当j=10时，dp[10]=max(dp[10], dp[7]+4)=7，含义是物品1加上物品2，总价值7。第三轮处理物品3（w=6,v=8），j=10时，dp[10]=max(7, dp[4]+8)=11，这代表物品1(3)加物品3(8)，总价值11。最后处理物品4，可以验证最优解是物品2+物品3，价值4+8=12，重量3+6=9，没有超过10。

手算完这个例子之后，我终于有一种“哦，原来这个表是这么填出来的”的感觉。所以我强烈建议，初学者遇到背包类问题，别急着写代码，先在纸上把dp表画出来，一格一格填一遍，填完之后你对“状态转移”四个字的理解会完全不一样。

3.4 01背包的常见变体：恰好装满和最大容量

01背包还有一个很容易在题目里踩到的变体：问的不是“最多能装多少价值”，而是“能不能恰好装满指定容量”。这种情况下，dp数组的初始化就不能全为0了，而是要改成dp[0]=0，其他为-inf或者-1，表示“无法恰好装满”。

我自己的理解是：“最多装多少”是允许剩余容量闲置的，所以任何容量初始都是0（什么也不装就是合法方案）；而“恰好装满”要求每一格容量都被用到，所以除了容量0，其他容量在没有合法方案前都是“不可达”的。这两种初始化方式，直接决定了dp数组的语义。以后做题时，第一件事就是仔细看题目要求的是“最大价值”还是“恰好装满”，这决定了初始化的写法。

4. 动态规划vs贪心vs回溯：三兄弟的适用边界

4.1 拿跳跃游戏II当试金石

学了一天动态规划之后，我回头看之前做过的一道题——跳跃游戏II，发现这道题完美地展示了动态规划和贪心的区别。题目是：给定一个非负整数数组，每个数字表示你在该位置可以跳跃的最大长度，问最少跳几次能跳到最后一个位置。

我当初是用贪心做的：每次在当前可到达范围内，选择一个能跳得最远的位置，然后跳过去。这个思路是对的，因为这道题有一个隐藏性质——跳跃次数是单调的，能跳过去的情况只需要尽量往前走就行，贪心不会错过全局最优。

但如果把题目稍微改一下，问你“跳到最后一个位置有多少种不同的跳跃方式”，贪心就彻底废了。因为这个问题需要把所有可能性都数出来，必须用动态规划：dp[i]表示跳到位置i的方式总数，dp[i] = sum(dp[j])对所有能从j跳到i的j求和。你看，同样是跳跃游戏，一个贪心能解决，一个必须上DP，原因就是前者只需要局部最远，后者需要统计全局路径。

这说明了一个道理：贪心是一种“短视”策略，它的正确性必须有严格的数学证明作为支撑；而动态规划是一种“全知”策略，它通过枚举所有状态来保证全局最优。能用贪心就优先用贪心，因为时间复杂度低、代码简单；但贪心失效时，动态规划是更稳妥的后手。

4.2 记忆化搜索和回溯剪枝的本质差异

还有一个我容易混淆的概念是：动态规划（尤其是记忆化搜索）和回溯+剪枝到底有什么区别？

回溯搜索的典型场景是全排列、N皇后这类问题，它的本质是深度优先遍历所有可能的解，遇到不满足条件的就剪枝。在这个过程中，同一个子问题可能会被重复计算多次，但没有办法直接改成一个“查表”的写法，因为你关心的是所有解的结构，而不是某个数值的最优值。

而动态规划面对的是一个“最优化问题”或者“计数问题”，答案是一个数。既然只是一个数，就可以记录下来供后续状态复用。从这个角度说，动态规划是“有记忆的回溯”——它把重复计算的子问题结果缓存下来，从而把指数级的时间复杂度降为多项式级。

我自己的做题经验是：拿到一道题，先看它要什么。如果要的是“所有可行方案”，那大概率是回溯；如果要的是“最少次数/最大价值/方案总数”，那大概率是动态规划。这个判断方法虽然不是100%精确，但作为第一直觉非常管用。

4.3 动态规划的优化方向：状态压缩和空间优化

聊完和其他算法的对比，再回到动态规划本身。今天我在写代码时发现，就算你状态转移方程写对了，代码也未必能跑过大数据量，因为空间复杂度可能会爆。比如二维dp的O(n*W)，n和W稍微大一点就直接内存溢出了。

常见的优化思路有两种。第一种是滚动数组/一维化，就像01背包那样，把二维dp压缩成一维，因为当前行只依赖上一行的值，更早的值就没用了。第二种是状态压缩DP，用在“棋盘覆盖”“旅行商”这类题目中，把某个维度的状态编码成一个二进制整数，从而把所有状态压缩到一个数组里。这种方法有点难，但它会打开动态规划的另一个世界，我打算后面专项去啃。

我的建议是：入门阶段先别追求花哨的优化，老老实实把二维dp写对，再去学空间压缩。因为我踩过的坑是——用一维滚动数组写错之后很难调试，因为不知道是状态定义错了还是遍历顺序错了。二维版本虽然占用空间大，但每个值都对应一个明确含义，查错容易得多。

5. 动态规划刷题时的几个高频坑点

5.1 初始化错误：inf和-1的选择

在入门动态规划的前两周，我几乎每一次WA（Wrong Answer）都出在初始化上。最常见的问题就是把dp数组初始化为0或-1，导致状态转移方程的结果被污染。

这里我总结出一个经验法则：如果你的状态是“最小值/最少次数”，其他状态必须初始化为一个大数（inf）；如果你的状态是“最大值/最大价值”，其他状态可以初始化为0。但是，如果题目要求“恰好装满”，初始化规则会变——除了dp[0]，其他要初始化为负无穷或-1，同时更新时要判断前一个状态是否可达。这个规则不背下来，光靠临场推理很容易出错。

5.2 遍历顺序：正序和倒序的永恒谜题

今天做01背包，被遍历顺序折磨得不轻。我后来整理了一套“判断帽子戏法”：

• 01背包：容量从大到小遍历，防止同一物品被重复使用
• 完全背包（每件物品可以无限用）：容量从小到大遍历，允许覆盖当前物品的新状态
• 二维dp：遍历顺序通常无所谓，因为当前格子的更新依赖的是上一行的值，不会冲突

这套规律不是死记硬背，而是理解了“dp[j-w[i]]代表的是旧状态还是新状态”之后自然得出的。我建议你亲自跑一个正序和倒序的对比测试，观察输出差异，那种“哦，原来差在这里”的感觉，比看十篇教程都管用。

5.3 状态定义不清导致转移方程写不出来

还有一种情况是——dp数组的语义没定义对，导致方程怎么都写不顺畅。比如“最长递增子序列”这道题，dp[i]如果定义成“前i个元素的最长递增子序列长度”，你很难写出转移方程；但如果你把它定义为“以第i个元素结尾的最长递增子序列长度”，转移就自然了：dp[i] = max(dp[j] + 1)对所有满足j < i且nums[j] < nums[i]的j。

所以我建议在动笔之前，先花五分钟把状态定义写清楚，想清楚dp[i]到底“代表什么含义”“下标的范围是多大”“最终答案怎么取”。这三个问题想明白了，代码基本就水到渠成了。状态定义是所有动态规划题里最重要的一步，也是稍纵即逝的灵感，建议想明白后立刻记下来。

6. 我的动态规划学习方法和工具推荐

6.1 如何用纸笔推导一份“状态转移图”

我给所有初学者的第一个建议就是：买一叠A4纸，或者开一个画板App，遇到动态规划题，先画状态转移表，再写代码。不要一上来就打开编译器。

比如做最少硬币问题时，我会把amount从0到11的格子全部画出来，然后一个硬币一个硬币地去填。填的过程中我会发现，有些值会反复被更新，有些则一次到位。这个“填表”的过程，就是你在建立“状态”和“转移”的直觉。

到了01背包，我会把物品编号作为行、容量作为列，画一个n行W列的表格，然后一行一行地填。填完之后，我甚至能指出“最优解是由哪几个格子路径组成的”。这个能力在面试时非常加分，因为面试官看到你能手动推导状态转移，就知道你不是在背模板。

6.2 从刷题网站到调试技巧：我的实操工具清单

如果你跟我一样是自学，我建议准备三样东西：

• LeetCode或者类似OJ平台：动态规划的题量很大，按照“入门-背包-序列型-区间型”的顺序刷题，每天3-5道即可
• 本地Python环境：不要只在网页上写代码，本地环境方便你打印dp表调试。我常用的调试手段是在循环里打印整个dp数组，看每个状态在每一轮之后长什么样
• 一个记录模板的笔记工具：不是让你背模板，而是记录“哪种题型对应哪种状态定义和遍历顺序”。我会把每道题的关键状态定义、转移方程、初始化方式、复杂度记下来，形成一个自己的速查手册

这里特别推荐一个调试技巧：在循环里加一行print(dp)，观察每一轮结束后的dp数组值。很多动态规划题的错误一眼就能看出来——比如某个值突然变得离谱大，那一定是初始化或者遍历顺序出了问题。

6.3 适合新手的第一组动态规划题目单

最后，我把自己刷过的、认为最适合新手的动态规划题目单整理一下，按难度递增排列：

1. 爬楼梯（入门状态转移）
2. 打家劫舍（一维dp经典）
3. 最长递增子序列（状态定义技巧）
4. 最少硬币（完全背包思想）
5. 01背包（滚动数组+遍历顺序）
6. 分割等和子集（01背包变体）
7. 最长公共子序列（二维dp）
8. 编辑距离（高难度综合）

我个人是从第1题开始，刷到第4题时就有一种“好像摸到门道了”的感觉，到第6题时已经能独立写出转移方程。如果你也正在这个阶段，不用急，一天搞懂一题，比一天刷十题但什么都不懂要强得多。

7. 一点个人心得：别怕“想不明白”，它只是个过程

今天day44的学习，最大的收获并不是我掌握了多少种动态规划的套路，而是我终于接受了一个事实：动态规划的“状态”不是靠看出来的，是靠大量的试错和推导磨出来的。

我在学习过程中经常遇到一种情况——状态转移方程怎么都写不出来，或者写出来了但过不了样例。以前我可能会烦躁、怀疑自己智商不够，但现在我明白了，这不是智商问题，而是“思维肌肉”还没练出来。每卡一次壳，其实都是在强化对状态和转移的理解。

如果你也正在被动态规划折磨，我的建议很简单：先别追求最优解，先把一个能跑的朴素版本写出来，哪怕空间复杂度爆炸，哪怕是递归+备忘录，都没关系。能跑通，就已经比“只会空想”强了几个层次，然后再一步步优化。这个过程可能很慢，但它绝对值得。动态规划这东西，你只要熬过前面最黑暗的一周，后面每做一道新题，都会有“原来如此”的爽感。