动态规划问题
动态规划问题
前言
这里总结一套解决这类问题的思维框架，希望能够成为解决动态规划问题的一部指导方针。
首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列、最小编辑距离等等。既然是求最值，那么核心问题是什么呢？这里核心问题就是穷举。因为求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。
穷举
动态规划的穷举有点特别，因为这类问题存在重叠子问题，若保利穷举的话效率会及其低下，所以需要备忘录或者DPtable来优化穷举过程，避免不必要的计算。
而且动态规划问题还存在最优子结构，才能通过子问题的最值得到原问题的最值。另外，穷举所有可行解其实不是一件容易的事，只有列出正确的状态转移房产才能正确地穷举。这里就有三个特征：
- 重叠子问题
- 最优子结构
- 状态转移方程
一般列出状态转移方程是最难的，这里提供一个思维框架来辅助思考：
按上面的套路走，最后的结果就可以套这个框架：
# 初始化base case
dp[0][0][...] = base
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
这里通过斐波那契数列问题和凑零钱问题来详解。
斐波那切数列问题
这个问题有个明显特征就是子问题是重叠的。方法一就是暴力递归求解。
int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
递归是简单方便易于理解，但是十分的低效，会出现大量的重复计算。这里有个网站：算法执行过程可以查看递归的执行过程，从中就可以看出低效的问题。假设n=20，这里画出递归树：
graph TB;
a((f20))-->b((f19))
a-->c((f18))
b-->d((f18))
b-->e((f17))
c-->f((f17))
c-->g((f16))
d-->h((...))
e-->i((...))
h-->j((f1))
h-->k((f2))
i-->l((f1))
i-->m((f2))
f-->n((...))
g-->o((...))
可以看出但凡遇到需要递归处理的问题，最好画出递归树，从递归树上可以分析算法的复杂度，寻找算法低效的原因等等。
从递归树可以看出：要计算f20，就需要先计算子问题f19和f18，然后要计算f19就需要先计算f18和f17，以此类推。最后遇到f2和f1的时候，结果已知，就能直接返回结果，递归树不再向下生长了。
递归算法时间复杂度
就是用子问题个数乘以解决一个子问题需要的时间。
- 计算子问题个数，即递归树种节点的总数。显然二叉树节点总数为指数级别，所以子问题的个数为
O(2^n)。 - 计算解决一个子问题需要的时间，在本算法中，没有循环，只有一个加法，所以时间复杂度为
O(1)。
所以本问题的时间复杂度即为：O(2^n)，指数级别，存在几何爆炸风险。看递归树就知道了，存在大量重复计算问题，比如f18被计算了两次，而且看出f18这个子树递归量也很大，多算一遍，会耗费巨大的时间，更何况还不知f18这一个节点被重复计算，所以算法及其低效。带备忘录的递归算法
既然耗时问题是重复计算，那么我们可以造一个备忘录，每次算出某个子问题的答案后先记到备忘录里再返回；每次遇到一个子问题先去备忘录里面查一查，如果发现之前已经解决了就直接拿出来用，不用重新计算。
一般使用一个数组充当备忘录，也可以使用哈希表、字典。
现在，画出递归树，就可以看出备忘录到底做了什么。int fib(int n) { if (n < 1) return 0; vector<int> memo(n+1, 0); return helper(memo, n); } int helper(vector<int>&memo, int n) { if (n==0) return 0; if (n==1) return 1; if (memo[n] != 0) return memo[n]; memo[n] = helper(memo, n- 1) + helper(memo, n - 2); return memo[n]; }
实际上，带备忘录的递归算法，把一颗存在巨量冗余的递归树通过剪枝改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中的节点）的个数。
计算优化后的时间复杂度
- 子问题的个数：即图中的节点总数，由于本算法不存在冗余计算，子问题就f1、f2、f3…f20，数量和输入的n成正比，所以子问题个数为
O(n)。 - 解决一个子问题的时间，也是
O(1)。
所以本问题的的时间复杂度就是O(n)。比起暴力递归，简直就是降维打击。
这里求解的思路是：「自顶向下」的，动态规划却是「自底向上」。「自顶向下」
观察刚刚画的递归树，是从上向下延伸的，都是从一个规模较大的原问题比如f20，向下逐渐分解规模，知道f1和f2这两个base case，然后再逐层返回上去，这就叫「自底向上」「自顶向下」
反过来，我们从最底下，最简单问题规模最小的f1和f2开始往上推，知道推到我们想要的答案f20，这就是动态规划的思路，这也就是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。dp数组的迭代解法
可以将「备忘录」独立出来成为一张DB table表，在这种表上完成「自底向上」的推算。
可以看出这是先计算小的，再慢慢计算大的，最终得到复杂的结果。int fib(int n) { vector<int> dp(n, 0); dp[0] = 0; dp[1] = 1; for (int i=2; i < n; i++) { dp[i] = dp[i-1] + dp[i - 2]; } return dp[n-1]; }状态转移方程
你把f(n)看成自变量对应的一个状态，这个状态是有状态n-1和状态n-2相加转移而来，这就叫状态转移，仅此而已。
$$
f(n)=
\begin{cases}
0, n=0\
1, n=1\
f(n-1) + f(n-2), n >= 2\
\end{cases}
$$
其实只要能写出暴力解，那么在暴力解的基础上添加备忘录就能进一步优化。代码进一步优化
仔细观察上面的带备忘录的解法，发现其实只需要存前两步状态，就能得到下一步状态，不断更新前两部状态，那么下一步状态也就可以轻松计算出来了，这样进一步将空间复杂度优化为O(1)：
这个技巧就是所谓的「状态压缩」，如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据，上述例子就相当于把DP table 的大小从 n 缩小到 2。int fib(int n) { if (n == 0) { return 0; } if (n == 1) { return 1 } int prev = 0, curr = 1; for (int i = 2; i < n; i++) { int sum = prev + curr; prev = curr; curr = sum; } return curr; }凑零钱问题
先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 … ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。
比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
你认为计算机应该如何解决这个问题？显然，就是把所有肯能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。
暴力求解
首先，这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？你肯定不想看数学证明，我用一个直观的例子来讲解。
比如说，假设你考试，每门科目的成绩都是互相独立的。你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。
得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，“每门科目考到最高”这些子问题是互相独立，互不干扰的。
但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，数学分数高，语文分数就会降低，反之亦然。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。
回到凑零钱问题，为什么说它符合最优子结构呢？比如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10 的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案。因为硬币的数量是没有限制的，所以子问题之间没有相互制，是互相独立的。
PS：关于最优子结构的问题，后文动态规划答疑篇 还会再举例探讨。
那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？
1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。
2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。
3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。
4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数：
dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。
搞清楚上面这几个关键点，解法的伪码就可以写出来了：
# 伪码框架
def coinChange(coins: List[int], amount: int):
# 定义：要凑出金额 n，至少要 dp(n) 个硬币
def dp(n):
# 做选择，选择需要硬币最少的那个结果
for coin in coins:
res = min(res, 1 + dp(n - coin))
return res
# 题目要求的最终结果是 dp(amount)
return dp(amount)
根据伪码，我们加上 base case 即可得到最终的答案。显然目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1：
def coinChange(coins: List[int], amount: int):
def dp(n):
# base case
if n == 0: return 0
if n < 0: return -1
# 求最小值，所以初始化为正无穷
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
# 子问题无解，跳过
if subproblem == -1: continue
res = min(res, 1 + subproblem)
return res if res != float('INF') else -1
return dp(amount)
至此，状态转移方程其实已经完成了，以上算法已经是暴力解法了，以上代码的数学形式就是状态转移方程：
$$
dp(n)=
\begin{cases}
0, n=0\
-1, n<1\
min{dp(n-coin)+1 | coin \in coins}, n > 0\
\end{cases}
$$
至此，这个问题其实就解决了，只不过需要消除一下重叠子问题，比如 amount = 11, coins = {1,2,5} 时画出递归树看看：
graph TB; a(11)-->b(10) a-->c(9) a-->d(6) b-->e(9) b-->f(8) b-->g(5) c-->h(...) d-->i(...) e-->j(...) f-->k(7) f-->l(6) f-->m(3) g-->o(...)
子问题总数为递归树节点个数，这个比较难看出来，是O(n^k)，每个问题中包含一个for循环，复杂度是O(k)，所以总的复杂度是：O(k * n^k)，指数级别。
带备忘录的递归
类似之前斐波那契数列的例子，只需要稍加修改，就可以通过备忘录消除子问题：
def coinChange(coins: List[int], amount: int):
# 备忘录
memo = dict()
def dp(n):
# 查备忘录，避免重复计算
if n in memo: return memo[n]
# base case
if n == 0: return 0
if n < 0: return -1
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
if subproblem == -1: continue
res = min(res, 1 + subproblem)
# 记入备忘录
memo[n] = res if res != float('INF') else -1
return memo[n]
return dp(amount)
很显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，所以子问题总数不会超过金额数 n，即子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)
dp 数组的迭代解法
当然，我们也可以自底向上使用 dp table 来消除重叠子问题，关于「状态」「选择」和 base case 与之前没有区别，dp 数组的定义和刚才 dp 函数类似，也是把「状态」，也就是目标金额作为变量。不过 dp 函数体现在函数参数，而 dp 数组体现在数组索引：
dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。
根据我们文章开头给出的动态规划代码框架可以写出如下解法：
int coinChange(vector<int>& coins, int amount) {
// 数组大小为 amount + 1，初始值也为 amount + 1
vector<int> dp(amount + 1, amount + 1);
// base case
dp[0] = 0;
// 外层 for 循环在遍历所有状态的所有取值
for (int i = 0; i < dp.size(); i++) {
// 内层 for 循环在求所有选择的最小值
for (int coin : coins) {
// 子问题无解，跳过
if (i - coin < 0) continue;
dp[i] = min(dp[i], 1 + dp[i - coin]);
}
}
return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
总结
列出动态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。