动态规划入门
在正式讲一系列概念之前，我们需要先知道：什么是“动态规划”。
动态规划可以理解成：沿着“某个方向”进行递推。至于这个“方向”具体是什么，后文会继续解释。
既然是递推，那么就需要有一个“数组”来存储我们递推过程中得到的信息。这个数组，就是动态规划中最关键的 DP 数组。
递推的本质，是通过一系列“小问题”推出“大问题”。动态规划也是一样：我们先解决一些规模较小、情况较简单的问题，再利用这些结果，推出更大的问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、状态
接下来引入第一个概念：状态。
对于简单的动态规划题目来说，状态通常可以设计成：
> 在“某种情况”下的最优答案。
例如，有 nnn 个数字需要依次做决策，那么我们可以把状态设计成：
> 前 xxx 个数字已经做完决策时，能够得到的最优解。
对于一些更复杂的动态规划题目，状态不一定直接表示答案，也可以表示：
> 在“某种情况”下，我们需要保存的某些信息。
之后再通过这些信息，进一步求出最终答案。本文暂时不展开复杂情况。
为了方便理解，我们可以把每个“状态”看成图中的一个点。这个点里面存储的值，就是当前状态对应的答案或信息。
也就是说：
> 状态是点，DP 数组存的就是这个点上的值。
例如，dp[i]dp[i]dp[i] 就可以看成编号为 iii 的点上存储的值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、操作
接下来是第二个概念：操作。
这里的“操作”，不是指一整套复杂的过程，而是指最小的操作单元。我通常会把它称为“走一步”（上过课的应该有印象）。
那么，什么叫“最小”呢？
可以这样理解：
> 在状态图中，一个点通过一步操作，到达另一个点。
也就是说，一个状态可以通过一次操作变成另一个状态。在图中，这一步操作就可以看成一条 有向边。
例如：
状态A→状态B状态 A \rightarrow 状态 B 状态A→状态B
表示：
> 从状态 AAA 可以通过一步操作走到状态 BBB。
因此，动态规划其实可以理解成：
> 在状态图上，通过操作来建边，然后按照一定顺序计算每个状态的值。
从这个角度看，很多动态规划问题都很像在状态图上做某种“最短路”“最长路”或“路径计数”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、转移
有了“状态”和“操作”之后，第三个概念：转移，就很好理解了。
所谓转移，就是：
> 从一个状态出发，通过某个操作，到达另一个状态，并且更新另一个状态中的值。
也可以理解成：
> 从一个点，沿着一条有向边，走到另一个点，并改变那个点存储的答案。
这就是动态规划中的“状态转移”。
例如：
dp[v]=max(dp[v],dp[u]+w)dp[v] = \max(dp[v], dp[u] + w) dp[v]=max(dp[v],dp[u]+w)
可以理解成：
> 从点 uuu 走到点 vvv，这条边的边权是 www，于是尝试用 dp[u]+wdp[u] + wdp[u]+w 更新 dp[v]dp[v]dp[v]。
所以动态规划里的“转移方程”，本质上就是在描述：
> 图中哪些点之间有边，以及沿着这些边走时，点上的值如何变化。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、动态规划的本质
到这里，我们可以把动态规划理解成：
> 在“操作方向”上的递推。
状态表示当前走到了哪里，操作表示下一步可以怎么走，转移表示走过去之后如何更新答案。
所以，动态规划并不是一个特别神秘的东西。它本质上就是：
> 把问题拆成很多状态，然后按照某个方向，把这些状态一个一个推出来。
如果从图的角度理解，就是：
> 把每个状态看成一个点，把每个操作看成一条边，然后在这个状态图上求答案。
有些题目是在状态图上求最大路径权值。
有些题目是在状态图上求最小路径权值。
有些题目是在状态图上求路径数量。
因此，动态规划可以看成：
> 在一个特殊的状态图上做递推。
这里说它“特殊”，是因为动态规划中的状态图通常是有方向、有顺序的。我们会按照某种顺序，把前面的状态先算出来，再用它们去更新后面的状态。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、几个抽象概念的直观解释
有了“状态图”的理解之后，我们就可以更直观地解释动态规划中的几个抽象概念。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 重叠子问题
什么是“子问题”？
在状态图中，每一个状态都可以看成一个子问题。
什么是“重叠”？
就是有很多种情况都会到达同一个状态。
换句话说，在状态图中，这个点的入度比较多。
例如，状态 dp[i]dp[i]dp[i] 可能既可以由 dp[i−1]dp[i-1]dp[i−1] 转移过来，也可以由 dp[i−2]dp[i-2]dp[i−2] 转移过来：
i−1→ii-1 \rightarrow i i−1→i
i−2→ii-2 \rightarrow i i−2→i
多个小问题都会用到同一个状态，这就是重叠子问题。
动态规划之所以要用数组存储答案，就是为了避免重复计算这些状态。
从图上看，就是：
> 一个点可能会被很多条边指向，所以我们把这个点的答案存下来，后面再用的时候就不用重新算了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 无后效性
无后效性指的是：
> 一个状态一旦确定，它接下来能产生什么影响，只和这个状态本身有关，和它是怎么来的无关。
也就是说，不管当前状态是从哪个状态转移过来的，只要当前状态相同，那么它之后能够转移到哪些状态、产生什么贡献，都是一样的。
从图上看，就是：
> 只要到达了同一个点，那么从这个点出发的边就是固定的。
它不会因为你是从哪条边走过来的，就突然多出一些边，或者少掉一些边。
举个例子：
假设当前状态是“我饱了”，接下来要进行“消化”操作。
如果“吃饭吃饱”和“吃面吃饱”之后，消化时间完全一样，那么我们只需要记录“饱了”这个状态即可。
但如果吃饭和吃面的消化时间不一样，那么虽然当前都叫“饱了”，但它们之后的发展并不相同。
此时只记录“饱了”就不够了，因为状态还受到之前选择的影响，这就存在后效性。
所以，动态规划的状态设计必须保证：
> 当前状态包含了影响未来决策所需要的全部信息。
如果从图上理解，就是：
> 一个点能走向哪里，必须只由这个点本身决定，而不能依赖它是怎么走到这个点的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 最优子结构
最优子结构指的是：
> 大问题的最优解，可以由小问题的最优解推出来。
放到状态图里理解，就是：
> 当一个点的所有前置状态都计算完成后，我们就可以利用这些前置状态，推出当前点的最优值。
例如，如果有三条边指向点 vvv：
u1→vu_1 \rightarrow v u1 →v
u2→vu_2 \rightarrow v u2 →v
u3→vu_3 \rightarrow v u3 →v
那么我们只需要知道 u1,u2,u3u_1,u_2,u_3u1 ,u2 ,u3 这些点的最优值，就可以计算出 vvv 的最优值。
如果整个状态图是一个 DAG，也就是有向无环图，那么我们就可以按照某种顺序，从前往后把所有状态依次算出来。
这也是为什么动态规划通常需要确定一个“递推顺序”。
因为只有当前面的小问题都算完了，我们才能放心地去计算后面的大问题。
从图上理解就是：
> 一个点要等它前面的点都算完，才能开始计算自己。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、动态规划的步骤
有了前面的概念之后，我们再来看做动态规划题目的一般步骤。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 识别问题类型
首先要判断这道题是否适合用动态规划。
动态规划常见于两类问题：
> 最优化问题和计数问题。
所谓最优化问题，就是要求最大值、最小值、最少次数、最多方案、最小代价等。
例如：
* 最多能得到多少分；
* 最少需要多少步；
* 最小花费是多少；
* 最大收益是多少。
所谓计数问题，就是要求方案数。
例如：
* 有多少种走法；
* 有多少种选择方式；
* 有多少种合法方案。
当然，不是所有最优化问题和计数问题都一定是动态规划，但如果题目中出现了“前面怎么选会影响后面”“可以由小规模推出大规模”这类感觉，就可以优先往动态规划方向考虑。
从图上看，动态规划常见的目标就是：
* 求到达某个点的最大路径权值；
* 求到达某个点的最小路径权值；
* 求到达某个点的路径数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 设计状态
接下来要设计状态，也就是确定 DP 数组的含义。
从图的角度看，这一步就是：
> 确定图中的点是什么。
对于简单动态规划来说，可以先用一个比较直接的方法：
> 答案问什么，状态就尽量往什么方向设计。
例如，题目问“前 nnn 个数能得到的最大值”，我们就可以先尝试设计：
dp[i]dp[i] dp[i]
表示：
> 前 iii 个数已经处理完时，能够得到的最优答案。
如果题目问“走到第 nnn 级台阶有多少种方法”，我们就可以设计：
dp[i]dp[i] dp[i]
表示：
> 走到第 iii 级台阶的方案数。
也就是说，状态设计的第一步，不需要一开始就非常复杂，可以先从题目最终要求的答案出发。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 识别操作
状态设计出来之后，下一步是识别“操作”。
从图的角度看，这一步就是：
> 确定点和点之间有哪些边。
也就是思考：
> 当前状态可以通过哪些“一步操作”转移到其他状态？
或者反过来思考：
> 当前状态可以由哪些前面的状态转移过来？
例如，走楼梯问题中，如果每次可以走 111 级或 222 级，那么：
* 从第 i−1i-1i−1 级可以走一步到第 iii 级；
* 从第 i−2i-2i−2 级可以走一步到第 iii 级。
所以图中就有两类边：
i−1→ii-1 \rightarrow i i−1→i
i−2→ii-2 \rightarrow i i−2→i
状态是点，操作是边。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 确定转移方式
找到前驱状态之后，还要确定这些前驱状态如何合并成当前状态。
从图的角度看，这一步就是：
> 多条边指向同一个点时，这个点的值应该怎么更新。
有些题目是求方案数，那么通常是把所有可能来源加起来：
dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2] dp[i]=dp[i−1]+dp[i−2]
这相当于：
> 到达点 iii 的路径数量，等于所有能走到点 iii 的前驱点的路径数量之和。
有些题目是求最大值，那么通常是在所有来源中取最大：
dp[v]=max(dp[v],dp[u]+w)dp[v] = \max(dp[v], dp[u] + w) dp[v]=max(dp[v],dp[u]+w)
这相当于：
> 从所有能走到点 vvv 的边中，选出一条收益最大的路径。
有些题目是求最小值，那么通常是在所有来源中取最小：
dp[v]=min(dp[v],dp[u]+w)dp[v] = \min(dp[v], dp[u] + w) dp[v]=min(dp[v],dp[u]+w)
这相当于：
> 从所有能走到点 vvv 的边中，选出一条代价最小的路径。
因此，确定转移方式时，要看题目最终问的是什么：
* 问方案数，通常是加法；
* 问最大值，通常是取 max\maxmax；
* 问最小值，通常是取 min\minmin。
当然，真实题目里不一定这么简单，但这个方向是最常见的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 检查状态是否足够
在写转移时，经常会遇到一种情况：
> 明明状态设计出来了，但是发现转移写不出来。
这通常说明一个问题：
> 当前状态记录的信息不够。
也就是说，只用现在这个 DP 数组，无法判断下一步应该怎么走，或者无法确定当前状态的答案。
从图上看，就是：
> 你现在设计出来的点不够细，导致从这个点出发时，不知道有哪些边是合法的，或者边权不唯一（也就是存在后效性）。
这时，最简单，最直接，最不绕弯子，最暴力的就是把状态设计得更细致一些。
例如，原本只设计：
dp[i]dp[i] dp[i]
表示前 iii 个位置的最优答案。
但是后来发现，第 iii 个位置选没选，会影响后面的选择。
那么就可以多加一个维度：
dp[i][0],dp[i][1]dp[i][0], dp[i][1] dp[i][0],dp[i][1]
其中：
* dp[i][0]dp[i][0]dp[i][0] 表示前 iii 个位置处理完，并且第 iii 个位置不选时的最优答案；
* dp[i][1]dp[i][1]dp[i][1] 表示前 iii 个位置处理完，并且第 iii 个位置选择时的最优答案。
这样一来，状态点就从一类变成了两类：
(i,0),(i,1)(i, 0), (i, 1) (i,0),(i,1)
点变细之后，边也就更清楚了。
所以，动态规划的状态并不一定是一开始就能完美设计出来的。很多时候，我们是在尝试写转移的过程中，发现信息不够，然后再反过来修改状态。
可以总结成一句话（这句对于很多动态规划有着醍醐灌顶的作用，用过都说好）：
> 转移缺什么，状态就补什么。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 按顺序求解
最后一步，就是按照正确的顺序计算所有状态。
因为动态规划是用小问题推出大问题，所以我们必须保证：
> 计算当前状态之前，它依赖的状态已经算完了。
例如，dp[i]dp[i]dp[i] 依赖 dp[i−1]dp[i-1]dp[i−1] 和 dp[i−2]dp[i-2]dp[i−2]，那么我们就应该从小到大枚举 iii。
从状态图的角度看，这其实就是在按照图上的依赖关系求解。
如果把每个状态看成一个点，把转移看成一条有向边，那么我们要做的就是：
> 按照有向边的方向，把所有状态依次算出来。
这个顺序本质上就是一种拓扑顺序。
对于初学阶段，可以先简单理解成：
> 前面的状态先算，后面的状态再用前面的结果。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、例题
下面通过几个经典例题，来对应前面讲过的几个概念。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第一题：走楼梯
假设一共有 nnn 级台阶，每次可以走 111 级或 222 级，问走到第 nnn 级台阶有多少种方法。
这是一道非常典型的计数型动态规划。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 状态是点
我们可以设计状态：
dp[i]dp[i] dp[i]
表示：
> 走到第 iii 级台阶的方案数。
从图的角度看，每一级台阶都是一个点。
点 iii 表示：
> 当前已经走到了第 iii 级台阶。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 操作是边
每次可以走 111 级或 222 级，这也是我们能做的最小操作。
所以：
* 从第 i−1i-1i−1 级可以走 111 级到第 iii 级；
* 从第 i−2i-2i−2 级可以走 222 级到第 iii 级。
也就是图中有两条边：
i−1→ii-1 \rightarrow i i−1→i
i−2→ii-2 \rightarrow i i−2→i
这些边表示“走一步”的操作。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 转移是统计路径数量
因为题目问的是方案数，所以我们要求的是：
> 从起点走到点 iii 的路径数量。
所有能走到点 iii 的路径，都一定来自：
* 点 i−1i-1i−1；
* 点 i−2i-2i−2。
所以：
dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2] dp[i]=dp[i−1]+dp[i−2]
这里的加法表示：
> 到达点 iii 的路径数量，等于所有前驱点的路径数量之和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 小结
走楼梯从状态图角度理解就是：
* 点：第 iii 级台阶；
* 边：走 111 级或走 222 级；
* dp[i]dp[i]dp[i]：到达点 iii 的路径数量；
* 目标：求到达点 nnn 的路径数量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第二题：打家劫舍
假设有一排房子，每个房子里有一些钱。小偷不能偷相邻的两个房子，问最多能偷多少钱。
这是一道典型的最优化动态规划。
这道题的关键限制是：
> 不能偷相邻的两个房子。
也就是说，当我们走到第 iii 个房子时，能不能偷它，取决于前一个房子有没有被偷。
所以我们不能只把状态设计成“处理到第 iii 个房子”，还需要记录当前这个房子是否被偷。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 状态是点
从图的角度来看，我们可以把每个状态看成一个点：
(i,0),(i,1)(i, 0), (i, 1) (i,0),(i,1)
其中：
* (i,0)(i, 0)(i,0) 表示：处理完前 iii 个房子，并且第 iii 个房子不偷；
* (i,1)(i, 1)(i,1) 表示：处理完前 iii 个房子，并且第 iii 个房子偷。
对应到 DP 数组中就是：
dp[i][0],dp[i][1]dp[i][0], dp[i][1] dp[i][0],dp[i][1]
其中：
* dp[i][0]dp[i][0]dp[i][0] 表示到达状态 (i,0)(i, 0)(i,0) 时，能够得到的最大金额；
* dp[i][1]dp[i][1]dp[i][1] 表示到达状态 (i,1)(i, 1)(i,1) 时，能够得到的最大金额。
这里之所以要拆成两个点，是因为：
> 第 iii 个房子偷没偷，会影响后面的边怎么连。
如果只用一个点表示“处理到第 iii 个房子”，我们就不知道第 i+1i+1i+1 个房子还能不能偷。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 操作是边
接下来考虑状态之间的边，也就是一步操作。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
如果第 iii 个房子不偷，那么第 i−1i-1i−1 个房子偷不偷都可以。
所以图中有两条边：
(i−1,0)→(i,0)(i-1, 0) \rightarrow (i, 0) (i−1,0)→(i,0)
(i−1,1)→(i,0)(i-1, 1) \rightarrow (i, 0) (i−1,1)→(i,0)
这两条边表示：
> 不管前一个房子偷没偷，我现在这个房子都可以选择不偷。
因为第 iii 个房子不偷，所以金额不会增加。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
如果第 iii 个房子偷，那么第 i−1i-1i−1 个房子一定不能偷。
所以图中只有一条边：
(i−1,0)→(i,1)(i-1, 0) \rightarrow (i, 1) (i−1,0)→(i,1)
这条边表示：
> 只有当前一个房子不偷时，我现在这个房子才能偷。
因为偷了第 iii 个房子，所以金额会增加 a[i]a[i]a[i]。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 转移是求最大路径权值
现在我们把每条边看成一次选择。
* 选择“不偷第 iii 个房子”，边权是 000；
* 选择“偷第 iii 个房子”，边权是 a[i]a[i]a[i]。
那么这道题就变成了：
> 在状态图中，从左往右走，求能获得的最大路径权值。
如果走到 (i,0)(i,0)(i,0)，说明第 iii 个房子不偷。
它可以从两个状态转移过来：
(i−1,0)→(i,0)(i-1,0) \rightarrow (i,0) (i−1,0)→(i,0)
(i−1,1)→(i,0)(i-1,1) \rightarrow (i,0) (i−1,1)→(i,0)
所以：
dp[i][0]=max(dp[i−1][0],dp[i−1][1])dp[i][0] = \max(dp[i-1][0], dp[i-1][1]) dp[i][0]=max(dp[i−1][0],dp[i−1][1])
如果走到 (i,1)(i,1)(i,1)，说明第 iii 个房子偷。
它只能从 (i−1,0)(i-1,0)(i−1,0) 转移过来：
(i−1,0)→(i,1)(i-1,0) \rightarrow (i,1) (i−1,0)→(i,1)
所以：
dp[i][1]=dp[i−1][0]+a[i]dp[i][1] = dp[i-1][0] + a[i] dp[i][1]=dp[i−1][0]+a[i]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 最终答案
处理完所有房子后，最后一个房子可以偷，也可以不偷。
所以答案是两个终点状态中的最大值：
max(dp[n][0],dp[n][1])\max(dp[n][0], dp[n][1]) max(dp[n][0],dp[n][1])
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 小结
打家劫舍从状态图角度理解就是：
* 点：(i,0)(i,0)(i,0) 和 (i,1)(i,1)(i,1)；
* 边：表示第 iii 个房子偷或不偷；
* 边权：偷则增加 a[i]a[i]a[i]，不偷则增加 000；
* dp[i][0]dp[i][0]dp[i][0]：到达点 (i,0)(i,0)(i,0) 的最大收益；
* dp[i][1]dp[i][1]dp[i][1]：到达点 (i,1)(i,1)(i,1) 的最大收益；
* 目标：求所有终点状态中的最大路径权值。
这就是“状态细化”的思想：
> 当一个状态无法确定后续能走哪些边时，就要把状态拆得更细。
在本题中，转移时缺少的信息是“当前房子有没有被偷”，所以我们增加了一维状态来记录这个信息。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第三题：找零问题
假设有若干种硬币面值，每种硬币可以使用无限次。现在要凑出金额 nnn，问最少需要多少枚硬币。
这是一道最小值动态规划。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 状态是点
我们可以设计状态：
dp[i]dp[i] dp[i]
表示：
> 凑出金额 iii 最少需要多少枚硬币。
从图的角度看，每一个金额都是一个点。
点 iii 表示：
> 当前已经凑出了金额 iii。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 操作是边
每次我们可以选择一枚硬币。
假设这枚硬币的面值是 vvv。
如果当前已经凑出了金额 i−vi-vi−v，再加入一枚面值为 vvv 的硬币，就可以凑出金额 iii。
所以图中有一条边：
i−v→ii-v \rightarrow i i−v→i
这条边表示：
> 选择一枚面值为 vvv 的硬币。
因为使用了一枚硬币，所以这条边的边权是 111。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 转移是求最短路径
由于题目问的是最少需要多少枚硬币，所以我们要求的是：
> 从金额 000 走到金额 nnn 的最短路径长度。
如果最后一枚硬币的面值是 vvv，那么它一定是从金额 i−vi-vi−v 转移到金额 iii。
因此：
dp[i]=min(dp[i],dp[i−v]+1)dp[i] = \min(dp[i], dp[i-v] + 1) dp[i]=min(dp[i],dp[i−v]+1)
这里的 +1+1+1 表示：
> 又使用了一枚硬币。
这里的 min\minmin 表示：
> 在所有能够到达金额 iii 的方式中，选择硬币数量最少的一种。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 小结
找零问题从状态图角度理解就是：
* 点：金额 iii；
* 边：选择一枚硬币；
* 边权：每选一枚硬币，代价为 111；
* dp[i]dp[i]dp[i]：从金额 000 到金额 iii 的最短路径长度；
* 目标：求从 000 到 nnn 的最短路径长度。
所以找零问题本质上就是：
> 在金额构成的状态图上，求到达目标金额的最小代价。
最后，感谢 codex\text{codex}codex 先生的润色。
