动态规划总结

极客时间动态规划面试宝典，结合个人理解的总结。

学习动态规划前言

一般情况下，我们开发或者处理数据结构相关问题时：

你本能地到工具函数或者库函数中寻找有没有现成的工具。如果问题得到快速解决，它是不是迅速就成了过眼云烟？
如果这个问题看起来比较棘手，它不是一个典型的算法问题，那么就寻求搜索引擎的帮助，或者干脆访问 Stack Overflow 这样的“智库”寻找前人留下的解决方案？

DP需要掌握的

DP的规律或特征：寻找子问题、递归求解、重叠子问题与无后效性、状态存储。

理解判断标准：哪些问题应该使用动态规划来解，而哪些不应该或不能使用动态规划来解。

动态规划的小结

DP需要的

Greedy问题

Greedy算法，卜老师说过不应该翻译为贪心算法，而是应该翻译为 ==“短视”== 算法，也就是只考虑当前拿到的最优，即局部最优选择，而非整体最优选择。但是优势局部最优就是全局最优。

Greedy的基本思路：

根据问题来建立数学模型，一般面试题会定义一个简单模型；

把待求解问题划分成若干个子问题，对每个子问题进行求解，得到子问题的局部最优解；

把子问题的局部最优解进行合并，得到最后基于局部最优解的一个解，即原问题的答案。

DP和Greedy的异同

相同点

皆典型用于解决优化问题
- DP不止可以用来求解最优化问题，还可以求解如p-value问题
可分，子问题最优解可用于佐证原问题的最优解
有optimal substructure
每个greedy后都有动态规划，尽管那有点笨重
Beneath every greedy algorithm, there is almost always a more cumbersome dynamic programming solution CRLS
推荐看算法导论贪心那一节
注意算法导论是手册

不同点

DP需要枚举所有的决策项，且最优决策项需要回溯
greedy不需要回溯，即可知道locally optimal

回溯

很多时候都用回溯搭配Greedy，但其实回溯应该算是最基本的DP的方式。

DP和分治

动态规划和分治思路有一点类似，都是需要把大问题分解为子问题，再将子问题的解进行合并起来求原问题的解。

动态规划后面子问题需要依赖前面求解的子问题的结果，并且动态规划一般需要枚举所有的子问题，通过维护一个表来减少重复运算。

DP问题

动态规划——解决最优问题
- 1 仍然是从最简单的问题入手
- 2 能不能分
  - 解能否逐步构造
  - 目标函数能否分
    这一点和之前divide counter不一样
- 3 多步决策
  
  关键
  - 如何最优？回溯

递归

递归的优势：递归形式的求解几乎就是简单的把题设中的函数表达式照搬过来，可以认为从数学意义上讲，递归更直观，且易于理解。

枚举与递归

一些问题需要枚举所有方案的组合，然后看这些组合是否是最优解，如果枚举出所有组合呢？需要一定的策略来生成——递归。

递归与迭代：迭代就是循环，递归就是函数中再调用函数（或者理解为向更深处请求）。

堆栈与递归的状态存储

在计算机中，实现递归必须建立在堆栈的基础上，这是因为每次递归调用的时候我们都需要把当前函数调用中的局部变量保存在某个特定的地方，等到函数返回的时候再把这些局部变量取出来。

而用于保存这些局部变量的地方也就是堆栈了。得益于递归，我们通过堆栈实现了状态存储。

我可以理解为：递归就是一种存储当前状态的手段，所以说可以用递归的算法应该都可以用迭代。

递归与回溯

递归拥有天然的回溯能力，因为它用堆栈存储了之前的状态。

我记得递归也有其坏处，递归比较难优化，有些组合其实是不用全部访问到的。

貌似为备忘录算法再优化空间。

树形结构与深度优先搜索

递归的过程的确就是一个树形结构，而递归也就是一个深度优先搜索的过程，先找到下一步的解，然后再回退，如此往复。

所以我们可以这样理解递归：作为一个算法解决方案，它采用了深度优先搜索的策略，去搜索所有可能的组合，并得到最优解的最优化问题。

如果在每个节点上加上当前这个节点求得的组合结果，就可以用递归树表示求解的组合空间。

优化暴力递归：简枝与优化

利用预设条件减少搜索路径，优化最优组合搜索方案（硬币的优化），这种做法感觉像是在暴力递归的前面装了一层调用的部分。

利用重叠子问题，避免重叠子问题的计算。这应该是DP的进一步思路。

备忘录

备忘录在于解决重叠子问题中的大量重复计算，提高算法效率。

提示：递归问题最好画递归树，而不是在脑海中模拟，树太大可以尝试画出主要的分支路径。

“备忘”二字就是当遇上一个子问题时，不是直接去递归求解，而是先去备忘录中查一下。

对于备忘录，可以考虑使用以下两种数据结构：

数组（Array），通常对于简单的问题来说，使用一维数组就足够了。一些复杂的存储过程需要二维甚至三维数组。

哈希表（Hash table），如果存储的状态不能直接通过索引找到需要的值（比如斐波那契数列问题，就可以直接通过数组的索引确定其对应子问题的解是否存在，如果存在就拿出来直接使用）。比如当使用了更高级的数据结构而非简单的数字索引，那么还可以考虑使用哈希表，即字典来存储中间状态，来避免重复计算的问题。

重叠子问题处理模式

假设面试问题是这样的：当目标为 x，其中 x 可能是一个任意长度的向量，目标可能包含多个元素，求最优解 F(x)。举个例子，比如在硬币这个问题里，x 就是硬币总额度，F(x) 就是最少的硬币数量。

同时，我们还需要知道问题是求最小值还是最大值，并以此来定义我们的数值函数 G(t)。如果求最小值，那么 G 是 min，如果求最大值，那么 G 就是 max。

除此之外，我们还需要通过当前的问题获得后续的一系列子问题，假定当前得到子问题的参数为 c，得到后续子问题的函数是 S，那么这个函数就是 S(x, c)。

接着，我们就可以用 F(S(x, c)) 来求得子问题的结果。

我们再定义一个函数 V(x)，该函数可以聚合当前参数 c 和当前子问题的结果。最后，我们还要定义每一步如何与子问题进行叠加。定义一个叠加函数 H(x)。

综上所述，最后得到如下求解公式：
$$
F(x)=H(G(V(F(S(x,c)),c)))
$$
因此，当解决类似问题时，只需要把问题套用到上面的公式（框架）中，就能用一个递归函数来描述所有的问题。可以尝试把斐波那契数列和硬币问题分别套入这个模型，就知道后面的问题定义该怎么举一反三了。

在定义好问题后，就可以编写基于递归算法的代码了。不过需要注意，上面的公式并不包含边界值的处理。所谓的边界值就是无法再分解为子问题的子问题。

比如在硬币找零问题中，x 为 0 的时候就是一个所谓的边界值。只要处理好递归函数和边界值，我们就能一通百通了。

说人话就是，在递归过程中，传递一个数据结构（数组）去存重复的部分。

重叠子问题缓存的限制

有些问题虽然看起来像包含“重叠子问题”的子问题，但是这类子问题可能具有后效性，但我们追求的是无后效性。所谓无后效性，指的是在通过 A 阶段的子问题推导 B 阶段的子问题的时候，我们不需要回过头去再根据 B 阶段的子问题重新推导 A 阶段的子问题，即子问题之间的依赖是单向性的。

如果一个问题可以通过重叠子问题缓存进行优化，那么它肯定都能被画成一棵树。

方案弊端

占据内存较大，需要在时间与空间中寻求一个平衡。

总结备忘录解法

用数组或哈希表来缓存已解的子问题答案，并使用自顶向下的递归顺序递归数据；
基于递归实现，与暴力递归的区别在于备忘录为每个求解过的子问题建立了备忘录（缓存）；
为每个子问题的初始记录存入一个特殊的值，表示该子问题尚未求解（如无此记录，或像求解斐波那契数列题目中那样初始化成 0）；
在求解过程中，从备忘录中查询。如果未找到或是特殊值，表示未求解；否则取出该子问题的答案，直接返回。

动态规划

动态规划问题一定具备以下三个特征：

重叠子问题：在穷举的过程中（比如通过递归），存在重复计算的现象；
无后效性：子问题之间的依赖是单向性的，某阶段状态一旦确定，就不受后续决策的影响；
最优子结构：子问题之间必须相互独立，或者说后续的计算可以通过前面的状态推导出来。

最优子结构

也就是子问题之间必须相互独立。

比如：🍎和🍌的折扣只能同时享有一个，那么这就不是独立的，不符合最优子结构。

当有最优子结构的时候：如果你准备购买了 5 斤折扣苹果，那么这个价格（即子问题）就被确定了，继续在购物车追加 3 斤折扣香蕉的订单，只需要在刚才的价格上追加折扣香蕉的价格，就是最低的总价格（即答案）。

初始化状态和状态参数

初始化状态：穷举算法（包括递归在内）的终止条件。

比如硬币找零的问题，初始化状态为金额为0时。

状态参数：子问题与原问题之间会发生变化的变量。

当硬币数量和面值是制定或者不受限制的时候，它们不需要作为变量，唯一需要不断传递的是“状态参数”，在这里是剩余金额k，状态参数逼近初始化状态的过程，即为状态转移。

一个传统的思路：初始化状态 -> 确定状态参数 -> 设计决策。

DP和递归

从理论上说，虽然带备忘录的递归算法与动态规划解法的时间复杂度是相同规模的，但在计算机编程的世界里，递归是依赖于函数调用的，而每一次函数调用的代价非常高昂。

递归调用是需要基于堆栈才能实现的。而对于基于堆栈的函数调用来说，在每一次调用的时候都会发生环境变量的保存和还原，因此会带来比较高的额外时间成本。这是无法通过时间复杂度分析直接表现出来的。

递归是==“自顶向下”==的。

状态缓存与循环

自顶向下的备忘录递归算法，每次都需要查询子问题是否已经被计算过。

自顶向下的思路是：从目标问题开始，不断将大问题拆解成子问题，然后再继续不断拆解子问题，直到子问题不可拆解为止。通过备忘录就可以知道哪些子问题已经被计算过了，从而提升求解速度。

==自底向上==就是从底层的子问题向上进行求解，这也是“从最简单的case入手”。

通用的动态规划

初始化状态：由于动态规划是根据已经计算好的子问题推广到更大问题上去的，因此我们需要一个“原点”作为计算的开端。在硬币找零问题中，这个==初始化状态==是 memo[0]=0；
状态：找出子问题与原问题之间会发生变化的变量。在硬币找零问题中，这个状态只有一个，就是剩余的目标兑换金额 k；
决策：改变状态，让状态不断逼近初始化状态的行为。在硬币找零问题中，挑一枚硬币，用来凑零钱，就会改变状态。

一般来说，状态转移方程的核心参数就是状态。

接着，我们需要自底向上地使用备忘录来消除重叠子问题，构造一个备忘录（在硬币找零问题中，它叫 memo。为了通用，我们以后都将其称之为 DP table）。

什么问题可以用动态规划

求“最”优解问题（最大值和最小值）

这样的问题一般都会让你求最大子数组、求最长递增子数组、求最长递增子序列或求最长公共子串、子序列等等。不知道你发现没有，这些问题里都包含一个“最”字，如果出现了这个字，那么你就该警惕它是否是动归问题。那具体怎么判断呢？

优先考虑使用贪心算法的可能性；

然后是暴力递归进行穷举（但这里的数据规模不大）；

还是不行呢？选择动态规划！

和我之前总结的一样，DP往往可以去应对==”穷举“==问题。

几种经典的用DP求最优解问题：

乘积最大子数组
最长回文子串
最长上升子序列

求可行性（True 或 False）

如果有这样一个问题，让你判断是否存在一条总和为 x 的路径（如果找到了，就是 True；如果找不到，自然就是 False），或者让你判断能否找到一条符合某种条件的路径，那么这类问题都可以归纳为求可行性问题，并且可以使用动态规划来解。

几种经典的用DP求可行性的问题：

凑零兑换问题
字符串交错组成问题

求方案总数

给定一个数据结构和限定条件，让你计算出一个方案的所有可能的路径，那么这种问题就属于求方案总数的问题。

几种经典的用DP求方案总数的问题：

硬币组合问题
路径规划问题

这里有一个规律或者说现象需要强调，那就是求方案总数的动态规划问题一般都指的是求==“一个”==方案的所有具体形式。如果是求==“所有”==方案的具体形式，那这种肯定不是动态规划问题，而是使用传统递归来遍历出所有方案的具体形式。

就我为数不多的经验而言，“所有”字样，一般使用回溯，双指针等。

为什么这么说呢？因为你需要把所有情况枚举出来，大多情况下根本就没有重叠子问题给你优化。即便有，你也只能使用备忘录对遍历进行一个简单加速。但本质上，这类问题不是动态规划问题。

进一步确认DP

什么时候看起来可以用，但最好不用DP？

如果可以通过排序来做的问题，一般不需要DP，比如求数组最小的k个数。
数组不可交换时，往往不存在DP要求一的重叠子问题，比如八皇后问题。

按照我之前总结的：

子问题有类似的结构并且相互独立，后面的子问题需要前面的子问题的运算结果。

DP的常见套路

0-1背包问题


示例：

输入：W = 5, N = 3
     w = [3, 2, 1], v = [5, 2, 3]
输出：8
解释：选择 i=0 和 i=2 这两件物品装进背包。它们的总重量 4 小于 W，同时可以获得最大价值 8。

背包问题满足DP的特征：

重叠子问题：对于 0-1 背包问题来说，即便我们不画出求解树，也能很容易看出在穷举的过程中存在重复计算的问题。这是因为各种排列组合间肯定存在重叠子问题的情况；
无后效性：当我们选定了一个物品后，它的重量与价值就随即确定了，后续选择的物品不会对当前这个选择产生副作用。因此，该问题无后效性；
最优子结构：当我们选定了一个物品后，继续做决策时，我们是可以使用之前计算的重量和价值的，也就是说后续的计算可以通过前面的状态推导出来。因此，该问题存在最优子结构。

写出状态转移方程：

初始化状态（算法终止的条件）：背包容量为0的时候。

状态参数：当前背包内的物品数量 N 和背包还能装下的重量 W。

决策：max (放入该物品, 不放入该物品)。

状态转移方程：略

代码：

int dp(int[] w, int[] v, int N, int W) {
    // 创建备忘录
    int[][] dp = new int[N+1][W+1];
  
    // 初始化状态
    // 其实可以不需要初始化状态，因为int用new之后默认值为0
    for (int i = 0; i < N + 1; i++) { dp[i][0] = 0; }
    for (int j = 0; j < W + 1; j++) { dp[0][j] = 0; }
  
    for (int tn = 1; tn < N + 1; tn++) { // 遍历每一件物品
    for (int rw = 1; rw < W + 1; rw++) { // 背包容量有多大就还要计算多少次
        if (rw < w[tn]) {
          // 当背包容量小于第tn件物品重量时，只能放入前tn-1件
          dp[tn][rw] = dp[tn-1][rw];
        } else {
                // 当背包容量还大于第tn件物品重量时，进一步作出决策
          dp[tn][rw] = Math.max(dp[tn-1][rw], dp[tn-1][rw-w[tn]] + v[tn]);
        }
      }
    }
  
  return dp[N][W];
}

int solveDP() {
  int N = 3, W = 5; // 物品的总数，背包能容纳的总重量
  int[] w = {0, 3, 2, 1}; // 物品的重量
  int[] v = {0, 5, 2, 3}; // 物品的价值
  
  return dp(w, v, N, W); // 输出答案
}

进入编写函数主体循环的阶段，让我们看看每一次循环中是如何做决策的：

主循环分为两层，第 1 层遍历所有物品，也就是尝试放入每个物品；第 2 层遍历背包容量，也就是假定当前背包容量是 rw 的时候，求在背包容量为 rw 时，放入当前物品的最大价值；
如果背包容量小于当前物品价值，那么这个时候最大价值也就是当前容量不变，使用上一个物品的最大价值即可；
如果背包容量大于当前物品价值，那么这个时候最大价值也就是从以下两个决策中挑选：

a. 放入这个物品前的最大价值 + 当前物品价值和作为答案；

b. 不放入这个物品时，当前容量的最大价值作为答案。

转化为0-1背包问题

问题：有一堆石头，每块石头的重量都是正整数。每次从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x≤y。那么粉碎的可能结果如下：

1. 如果 x 与 y 相等，那么两块石头都会被完全粉碎；
2. 否则，重量为 x 的石头将会完全粉碎，而重量为 y 的石头的新重量为 y−x。

最后，最多只会剩下一块石头。返回此时石头最小的可能重量。如果没有石头剩下，就返回 0。


示例：

输入：[1, 2, 1, 7, 9, 4]
输出：
解释：Round 1: (2, 4) -> 2, 数组变成 [1, 1, 7, 9, 2]
     Round 2: (7, 9) -> 2, 数组变成 [1, 1, 2, 2]
     Round 3: (2, 2) -> 0, 数组变成 [1, 1]
     Round 4: (1, 1) -> 0, 数组为空，返回 0

我个人第一反应是先排序，然后大的去减去小的，也就是从数组两边入手。

精妙的转换：

首先，请你观察一下上面提供的示例。在示例中，第一步组合 2 和 4，求出 (4 - 2) = 2；第二步组合 7 和 9，求出 (9 - 7) = 2；第三步组合 2 和 2，求出 (2 - 2) = 0；最后第四步组合 1 和 1，同样得 0。我们把这个过程组合成一个式子，它看起来是这样的：
$$
1−(((4−2)−(9−7))−1)
$$
如果解开这些括号，就可以得到 1 - 4 + 2 + 9 - 7 - 1。再做一下简单的变换，就可以得到如下式子：
$$
1+2+9−1−4−7
$$
这个时候，我们可以把这个公式分成两组，一组是从数组中挑选出几个数字相加；然后，将另外几个数字相减，求两个数字的差。最后确保这个差最小。

从直觉上来说，如何确保两组数字之差最小呢？

我们可以看到如果一组数字接近所有数字之和的 1/2，那么两组数字之差肯定越小，比如上面的示例中所有数字之和是 24，所以一组数字是 12，另一组数字也是 12，最后肯定能得到最小值 0。

现在，假设有一个背包，背包的容量是 12（24/2）。接着，我们有一堆的物品，重量分别是 [1, 2, 1, 7, 9, 4]，注意我们设它的价值与重量相同。现在我们希望选出的物品放到背包里的价值最大，这样一来，我们就可以把这个题目转化成 0-1 背包问题了。

于是，可以写出如下状态转移方程：
$$
DP(tn,rw)=
\begin{cases}
0& \text{tn<=0}\
0& \text{rw<=0}\
DP(tn-1,rw),rw<w[tn] &\text{rw<w[tn]}\
max=(DP(tn-1,rw),DP(tn-1,rw-w[tn]+v[tn])) &\text{rw>w[tn]}
\end{cases}
$$

通用的动态规划

我觉得实用性不一定大，需要的更多是理解思想和练习。

一个动态规划问题是指它可以从大问题中找到无后效性的重叠子问题。所谓无后效行是指，其子问题不会双向依赖，只会单向依赖。否则，我们就无法确保子问题处理后，更大的问题一定能取到子问题的解。

对动态规划问题进行泛化统一建模，如果用数学语言描述就如下公式所示：
$$
f(x)=
\begin{cases}
d(x) &&&&{x\in{V_{1}}}\
g({v(f(s(x,c)}) &&&&c\in{values(x)}
\end{cases}
$$
我们该怎么理解这个公式呢？首先，我们需要考虑一些边界情况，如果输入向量 x，那么在边界组合 VI 中，用一个边界函数 d(x) 直接返回 f(x) 的值，就不需要再划分子问题了。比如在 0-1 背包问题中，当 tn 或 rw 小于等于 0 时，这个值就是 0。

否则，说明这是一个可以划分子问题的问题，那么我们就需要从可选组合 values 中取出用于划分子问题的备选值。需要牢记的是，在复杂问题中这个 values 可能不是一个一成不变的组合，它会随着当前状态 x 变化而变化。

接着，我们对每一个备选值 c（与上面的 x 类似，同样可能是一个向量），通过函数 s(x,c) 求得当前备选值的子问题的 x, c。然后，通过 f(s(x,c)) 得到这个子问题的结果。

再接着，我们通过子问题 v(f(s(x,c)),c) 的结果和当前备选值 c，来求得当前问题的解。因为我们有一系列的备选值 c，因此会得到一个当前问题的求解集合。

最后，我们通过最优化函数 g(t) 进行求解。比如原问题是求最小值，那么 g(t) 就是 min(t)；如果是求最大值，那么就是 max(t)。这两种是最为常见的函数，我们在前面的例题当中也都见过了。