动态规划

type

status

password

date

slug

summary

动态规划问题的一般形式就是求最值或者计数问题（例如，求问题有多少种解决方案；或者零钱的最小找兑方法），求解动态规划的核心问题是穷举。因为要求最值或者计数，肯定要把所有可行的答案穷举出来，然后在其中找最值或者统计所有的可行方案。

三要素

动态规划包括以下3个特点：

重叠子问题：动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

最优子结构：如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

另外，虽然动态规划的核心思想就是穷举，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。如果题目具有重叠子问题、最优子结构，相比于暴力穷举使用动态规划算法可以大大降低算法的复杂度。状态转移方程是动态规划中最难的部分，但是有一定的解题套路（单序列动态规划、双序列动态规划、矩阵动态规划、背包问题、博弈型、区间问题）。

解题关键

如果问题具有重叠子问题、最优子结构，使用动态规划可以提高算法效率。但是算法的具体实现应该考虑以下几个问题提

状态：分割子问题的限定状态

base case：先根据题目的限制条件来确定题目中给出的边界条件是否能直接推导出，如果不行也可以尝试从边界条件反推（举个例子：a(n)→a(2)有递推关系，但是a(2)→a(1)不符合上述递推关系，我们就可以考虑用a(1)来倒推出a(2)，然后将递推的终点设置为a(2)）;

状态转移方程：状态转移方程是动态规划中最难的部分，但是有一定的解题套路（
📏
单序列型、
🌒
双序列型、
🚔
矩阵坐标型、
🕓
背包型、
🎀
区间及其他类型）。

两种实现方式

自顶向下的备忘录法

此方法按自然的递归形式编写过程，但过程会保存每一个子问题的解（通常保存在一个数组或散代表中）。当需要一个子问题的解时，会首先检查了是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则按通常方式计算这个子问题。

自底向上

这种方法一般需要恰当定义子问题规模的概念，使得任何子问题的求解都只依赖于更小的子问题的求解。因而我们可以将此问题按规模排序，按由小至大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题，只需求解一次，当我们求解它时（也是第一次遇到它时）它的所有前提子问题都已求解完成。

状态压缩:当使用自底向上的时候，可能存在空间优化的余地。

💡

自底向上：有时候dp[i]表示为 A[0,...,i]的状态，且必须包含A[i]，此时最好用自底向上的方法，例如：题目LC300，因为此时需要回溯 dp[i] 之前的所有状态。注意遍历方向需要根据状态转移方程确定如回文字符串

自顶向下：如果初始状态不容易确定，那么最好用自顶向下，例如矩阵中的最长递增路径，知道边界条件是一个点，它四周的点都比它多大，此时它为0，此时边界条件不容易确定位置，状态转移方程也不容易写。

凑零钱

题目

给定 k 种面值的 coins，面值分别为 c1, c2 ... ck，每种硬币的数量无限；再给定一个总金额 amount。计算可以凑成总金额的最少硬币个数；如果没有任何一种硬币组合能够凑成总金额，算法返回 -1 。算法的函数签名如下：

输入： coins=[1, 2, 5], amount=11输出：3解释：11=5+5+1=11

你认为计算机应该如何解决这个问题？显然，就是把所有肯能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。

三要素说明

如图所示，节点表示amount（凑出纸币的面额）。分支处表示所需要的coin金额。

重叠子问题

如上图所示，如果要穷举出凑出11元的所有情况，会发现有大量的重复子问题，例如凑出橘色的9元，凑出粉色的5元。

最优子问题

为什么说它符合最优子结构呢？比如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10、9、6 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是1凑出11元的硬币数，从中选择最少的就是原问题的答案。

所以为了求出凑到11元所需要的最少硬币数，我们需要求解凑出10元、9元、6元所需要的最少硬币数。

状态转移方程

凑出 n 元最少所需要的硬币数，等于凑出（n-coin） 元最少所需的硬币数目，加上最后的 coin 这一枚。

编程

确定「状态」。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向目标金额靠近，所以唯一的「状态」就是目标金额 amount。

边界条件。目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。金额小于 0，直接返回 -1.

状态转移方程。

自顶向下（备忘录法）

题目要用最少数量的三枚硬币去凑11，因为有三种硬币，首先问题一定有最优解，所以可以转化为求分别凑10，9，6的子问题（subProblem）, 10又可以分为凑9，8，5的子问题，以此类推。经过穷举我们可以举出所有的情况，但如果如此暴力穷举，会造成效率低下，当硬币数量足够多，目标金额足够大，时间复杂度是指数级别的。这主要还是因为我们在不断的重复做一些之前已经做完的事情，所以我们要学会标记已经做过的东西。

我们用字典dic来标记已经做好的事情。在递归的时候如果发现前面 dic[n] 的值计算出来了就不再计算；如果未计算出来，则计算出来后保存在字典dic中，下次在调用 dp(n) 的时候就不会重新递归了。例如在计算 dp(10)的时候调用了 dp(5)，算出 dp(5) 后；再计算 dp(6) 调用了 dp(5) 的时候，就不用递归 dp(5) 了。

自低向上

回文字符串

题目

输入一个字符串 s，你可以在字符串的任意位置插入任意字符。如果要把 s 变成回文串，请你计算最少要进行多少次插入？函数签名如下：

比如说输入 s = "abcea"，算法返回 2，因为可以给 s 插入 2 个字符变成回文串 "abeceba" 或者 "aebcbea"。如果输入 s = "aba"，则算法返回 0，因为 s 已经是回文串，不用插入任何字符。

思路解析

首先，要找最少的插入次数，那肯定得穷举喽，如果我们用暴力算法穷举出所有插入方法，时间复杂度是多少？每次都可以在两个字符的中间插入任意一个字符，外加判断字符串是否为回文字符串，这时间复杂度肯定爆炸，是指数级。

那么无疑，这个问题需要使用动态规划技巧来解决。之前的文章说过，回文问题一般都是从字符串的中间向两端扩散，构造回文串也是类似的。

我们定义一个二维的dp数组，dp[i][j]的定义如下：对字符串s[i..j]，最少需要进行dp[i][j]次插入才能变成回文串。我们想求整个 s 的最少插入次数，根据这个定义，也就是想求 dp[0][n-1] 的大小（n 为 s 的长度）。

同时，base case 也很容易想到，当 i == j 时 dp[i][j] = 0，因为当 i == j 时 s[i..j] 就是一个字符，本身就是回文串，所以不需要进行任何插入操作。

接下来就是动态规划的重头戏了，利用数学归纳法思考状态转移方程。

状态转移方程

1、状态转移就是从小规模问题的答案推导更大规模问题的答案，从 base case 向其他状态推导嘛。如果我们现在想计算 dp[i][j] 的值，而且假设我们已经计算出了子问题 dp[i+1][j-1] 的值了，你能不能想办法推出 dp[i][j] 的值呢？

3、这个得分情况讨论，如果 s[i] == s[j] 的话，我们不需要进行任何插入，只要知道如何把 s[i+1..j-1] 变成回文串即可：翻译成代码就是这样：

4、如果 s[i] != s[j] 的话，就比较麻烦了，比如图四这种情况：

最简单的想法就是，先把 s[j] 插到 s[i] 右边，同时把 s[i] 插到 s[j] 右边，这样构造出来的字符串一定是回文串。PS：当然，把 s[j] 插到 s[i] 左边，然后把 s[i] 插到 s[j] 左边也是一样的，后面会分析。但是，这是不是就意味着代码可以直接这样写呢？如图五所示

💡

不对，比如右边这两种情况，只需要插入一个字符即可使得 s[i..j] 变成回文：

5、所以说，当 s[i] != s[j] 时，无脑插入两次肯定是可以让 s[i..j] 变成回文串，但是不一定是插入次数最少的，最优的插入方案应该被拆解成如下流程：

2、既然已经算出 dp[i+1][j-1]，即知道了 s[i+1..j-1] 成为回文串的最小插入次数，那么也就可以认为 s[i+1..j-1] 已经是一个回文串了，所以通过 dp[i+1][j-1] 推导 dp[i][j] 的关键就在于 s[i] 和 s[j] 这两个字符。

图三 s[i] == s[j] dp[i][j] = dp[i + 1][j - 1]

图六插入一个字符即可使得 s[i..j] 变成回文 — 图六插入一个字符即可使得 `s[i..j]` 变成回文

步骤一，做选择，先将 s[i..j-1] 或者s[i+1..j] 变成回文串。怎么做选择呢？谁变成回文串的插入次数少，就选谁呗。

步骤二，将 s[i..j] 变成回文。

如果你在步骤一中选择把 s[i+1..j] 变成回文串，那么在 s[i+1..j] 右边插入一个字符 s[i] 一定可以将 s[i..j] 变成回文；同理，如果在步骤一中选择把 s[i..j-1] 变成回文串，在 s[i..j-1] 左边插入一个字符 s[j] 一定可以将 s[i..j] 变成回文。

那么根据刚才对 dp 数组的定义以及以上的分析，s[i] != s[j] 时的代码逻辑如下：

综合起来，状态转移方程如下：

这就是动态规划算法核心，我们可以直接写出解法代码了。

代码实现

首先想想 base case 是什么，当 i == j 时 dp[i][j] = 0，因为这时候 s[i..j] 就是单个字符，本身就是回文串，不需要任何插入；最终的答案是 dp[0][n-1]（n 是字符串 s 的长度）。那么 dp table 如图八所示：

又因为状态转移方程中 dp[i][j] 和 dp[i+1][j]，dp[i][j-1]，dp[i+1][j-1] 三个状态有关，为了保证每次计算 dp[i][j] 时，这三个状态都已经被计算，我们一般选择从下向上，从左到右遍历 dp 数组，如图九所示：

完整代码如下：

现在这道题就解决了，时间和空间复杂度都是 O()。还有一个小优化，注意到 dp 数组的状态之和它相邻的状态有关，所以 dp 数组是可以压缩成一维的：

至于这个状态压缩是怎么做的，我们前文状态压缩技巧详细介绍过，这里就不展开了。