动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。相比回溯算法，动态规划可以非常显著地降低时间复杂度，提高代码的执行效率。那我们为什么需要动态规划？以及动态规划解题方法是如何演化出来的呢？我们先来看下面这两个经典的例子来初步了解下动态规划的思想。
动态规划入门
1. 0-1 背包问题
对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？之前我们讲了回溯算法的解决方案，也就是穷举搜索所有可能的装法，然后找出满足条件的最大值。但回溯算法的复杂度比较高，是指数级别的。那有没有什么规律可以有效降低时间复杂度呢？
我们假设背包的最大承载重量是 9。我们有 5 个不同的物品，每个物品的重量分别是 2，2，4，6，3。我们先用回溯算法的处理思想，把求解问题的过程用递归树画出来，就是下图这个样子：
递归树中的每个节点表示一种状态，借鉴回溯算法，我们用（index, currentWeight）来表示每个节点。其中，index 表示将要决策第几个物品是否装入背包，currentWeight 表示当前背包中物品的总重量。比如（2，2）表示我们将要决策第 2 个物品是否装入背包，在决策前，背包中物品的总重量是 2。
1.1 借助备忘录优化回溯算法
从递归树中我们可以发现，有些子问题的求解是重复的，比如图中 f(2, 2) 和 f(3,4) 都被重复计算了两次。此时，我们可以借助备忘录的解决方式，记录已经计算好的 f(index, currentWeight)，当再次计算到重复的 f(index, currentWeight) 时，可以直接从备忘录中取出来用，就不用再递归计算了，这样可以有效避免冗余计算。
代码实现
/** 每个物品的重量 */private final int[] itemWeight;/** 背包可承载的总容量 */private final int packageCapacity;/** 选择装入到背包中的物品的总容量 */private int maxSelectCapacity = 0;/** 备忘录,一维为物品，二维为重量 */private final boolean[][] mem = new boolean[itemWeight.length][packageCapacity + 1];private void put(int index, int currentWeight) {if (currentWeight == packageCapacity || index == itemWeight.length) {if (currentWeight > maxSelectCapacity) {this.maxSelectCapacity = currentWeight;}return;}// 通过备忘录记录重复状态,相同节点只会重复执行一次if (mem[index][currentWeight]) {return;}mem[index][currentWeight] = true;// 不选择当前物品put(index + 1, currentWeight);if (currentWeight + itemWeight[index] <= packageCapacity) {// 选择当前物品put(index + 1, currentWeight + itemWeight[index]);}}
实际上，这种解决方法已经跟动态规划的执行效率基本上没有差别了。但多一种方法就多一种解决思路，我们现在来看看动态规划是怎么解决的。
1.2 动态规划的求解思路
我们把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策完以后，背包中的物品的重量就会有多种情况，对应到递归树中，就是有很多不同的节点（状态）。我们把每一层重复的节点合并，只记录不同的状态，然后在基于上一层的状态集合，来推导下一层的状态集合。通过合并每一层重复的状态，保证了每一层不同状态的个数都不会超过 w 个（w表示背包的承载重量）。于是，我们就成功避免了每层状态个数的指数级增长。
我们用一个二维数组 states[n][w+1] 来记录每层可以达到的不同状态。第 0 个（下标从 0 开始）物品的重量是 2，有两种决策可能，要么装入背包，要么不装入背包，决策完之后会对应背包的两种状态，背包中物品的总重量是 0 或 2。我们用 states[0][0]=true 和 states[0][2]=true 来表示这两种状态。
第 1 个物品的重量也是 2，基于之前的背包状态，在这个物品决策完后有 3 个不同的状态，背包中物品的总重量分别是 0(0+0)，2(0+2 or 2+0)，4(2+2)。我们用 states[1][0]=true，states[1][2]=true，states[1][4]=true 来进行表示。以此类推，直到考察完所有的物品后，整个 states 状态数组就都计算好了。如下图所示。图中 0 表示 false，1 表示 true。我们只需要在最后一层，找一个值为 true 的最接近 w（这里是 9）的值，就是背包中物品总重量的最大值。
代码实现
/** 每个物品的重量 */
private final int[] weight;
/** 背包可承载的总容量 */
private final int w;
/** 状态数组,一维为物品，二维为重量 */
private final boolean[][] states = new boolean[weight.length][w + 1];
public int putItem2Package() {
// 第一行数据特殊处理，表示将第一个物品的选择或不选择两种方式的状态都设为true。有了第一行，才能推导出后面的
states[0][0] = true;
if (weight[0] <= w) {
states[0][weight[0]] = true;
}
// 循环剩余物品,计算状态
for (int i = 1; i < weight.length; i++) {
// 不把第i个物品放入背包
for (int j = 0; j <= w; j++) {
// 因为不放入，所以重量不会增加，保持和上一次放入时的重量一样
if (states[i - 1][j]) {
states[i][j] = true;
}
}
// 把第i个物品放入背包，且保证放入后不超过最大容量
for (int j = 0; j <= w - weight[i]; j++) {
// 放入后，重量增加
if (states[i - 1][j]) {
states[i][j + weight[i]] = true;
}
}
}
// 动态规划求解完成，取在状态范围内的最大值，逆序遍历获取最靠右的
for (int i = w; i >= 0; i--) {
if (states[weight.length - 1][i]) {
return i;
}
}
return 0;
}
实际上，这就是一种用动态规划解决问题的思路。我们把问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。
动态规划解法的时间复杂度
耗时最多的部分就是代码中的两层 for 循环，所以时间复杂度是 O(n*w)。n 表示物品个数，w 表示背包可以承载的总重量。因此，相比于回溯算法的指数级的时间复杂度 O(2n)，动态规划的时间复杂度要低很多。
根据 states 数组获取装入背包中的物品
状态 [i, j] 只可能从 [i-1, j] 或 [i-1, j-weight[i]] 两个状态推导过来。所以，我们就检查这两个状态是否是可达的，也就是 states[i-1][j] 或者 states[i-1][j-weight[i]] 是否是 true。如果 states[i-1][j] 可达，就说明我们没有把第 i 个物品装入背包，如果 states[i-1][j-weight[i]] 可达，那就说明我们把第 i 个商品装入了背包中。如果两个都可达，可以随意选择一个，然后继续迭代地考察其他物品是否被装入了背包中。
尽管动态规划的执行效率比较高，但我们需要额外申请一个 states[n][w+1] 二维数组，对空间的消耗比较多。所以，有时候我们会说，动态规划是一种空间换时间的解决思路。那有什么办法可以降低空间消耗吗？实际上，我们只需要一个大小为 w+1 的一维数组就可以解决这个问题。动态规划状态转移的过程，都可以基于这个一维数组来操作。
/** 每个物品的重量 */
private final int[] weight;
/** 背包可承载的总容量 */
private final int w;
/** 状态数组，这里采用一维数组，相当于合并了二维数组，因为我们只需要取最大值 */
private final boolean[] states;
public int putItem2Package() {
states[0] = true;
if (weight[0] <= w) {
states[weight[0]] = true;
}
// 动态规划
for (int i = 1; i < weight.length; i++) {
// j从大到小处理，避免for循环重复计算
for (int j = w - weight[i]; j >= 0; j--) {
if (states[j]) {
states[j + weight[i]] = true;
}
}
}
// 逆序遍历获取最靠右的，即为最大值
for (int i = w; i >= 0; i--) {
if (states[i]) {
return i;
}
}
return 0;
}
2. 0-1 背包问题升级版
我们刚刚讲的背包问题中，只涉及背包重量和物品重量。我们现在引入物品价值这一变量。那么对于一组不同重量、不同价值、不可分割的物品，我们选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少呢？
1.1 回溯算法思路
/** 每个物品的重量 */
private final int[] itemWeight;
/** 每个物品的价值 */
private final int[] itemValue;
/** 背包可承载的总容量 */
private final int packageCapacity;
/** 选择装入到背包中的物品的总价值 */
private int maxSelectValue = 0;
/**
* @param i 当前要装载物品的索引
* @param cw 当前背包已装载的重量
* @param cv 当前背包已装载的物品的总价值
*/
public void put(int i, int cw, int cv) {
// 如果装满了或者装完了
if (cw == packageCapacity || i == itemWeight.length) {
if (cv > maxSelectValue) {
this.maxSelectValue = cv;
}
return;
}
// 不选择当前物品
put(i + 1, cw, cv);
if (cw + itemWeight[i] <= packageCapacity) {
// 选择当前物品
put(i + 1, cw + itemWeight[i], cv + itemValue[i]);
}
}
针对上面的代码，我们画出如下递归树。在递归树中，每个节点表示一个状态。我们需要 3 个变量（i, cw, cv）来表示一个状态。i 表示将要决策第 i 个物品是否装入背包，cw 表示当前背包中物品总重量，cv 表示当前背包中物品总价值。
我们发现，在递归树中，有几个节点的 i 和 cw 是完全相同的，比如 f(2,2,4) 和 f(2,2,3)。在背包中物品总重量一样的情况下，f(2,2,4) 这种状态对应的物品总价值更大，因此，我们可以直接舍弃 f(2,2,3) 这种状态，只需要沿着 f(2,2,4) 这条决策路线继续往下决策就可以。也就是说，对于 (i, cw) 相同的不同状态，我们只需要保留 cv 值最大的那个，继续递归处理即可，其他状态不用再考虑了。
1.2 动态规划思路
我们还是把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个阶段决策完之后，背包中的物品的总重量以及总价值，会有多种情况，也就是会达到多种不同的状态。我们仍用一个二维数组 states[n][w+1] 来记录每层可以达到的不同状态。不过这里数组存储的值不再是布尔类型了，而是当前状态对应的最大总价值。我们把每一层中 (i, cw) 重复的状态（节点）合并，只记录 cv 值最大的那个状态，然后基于这些状态来推导下一层的状态。
/** 每个物品的重量 */
private final int[] weight;
/** 每个物品的价值 */
private final int[] value;
/** 背包可承载的总容量 */
private final int w;
/** 状态数组，一维是物品，二维是重量，数组值是相同重量下的最高价 */
private final int[][] states;
public int putItem2Package() {
states[0][0] = 0;
if (weight[0] <= w) {
states[0][weight[0]] = value[0];
}
// 动态规划，状态转移
for (int i = 1; i < weight.length; i++) {
// 不把第i个物品放入背包，此时价值不变
for (int j = 0; j <= w; j++) {
if (states[i - 1][j] > 0) {
states[i][j] = states[i - 1][j];
}
}
// 把第i个物品放入背包，且保证放入后不超过最大容量
for (int j = 0; j <= w - weight[i]; j++) {
if (states[i - 1][j] >= 0) {
// 获取同重量下价值最高的
int v = states[i - 1][j] + value[i];
if (v > states[i][j + weight[i]]) {
states[i][j + weight[i]] = v;
}
}
}
}
// 找出最大值
int maxValue = 0;
for (int i = 0; i <= w; i++) {
if (states[weight.length - 1][i] > maxValue) {
maxValue = states[weight.length - 1][i];
}
}
return maxValue;
}
动态规划理论
究竟什么样的问题适合用动态规划来解决呢？换句话说，动态规划能解决的问题有什么规律可循呢？我们把这部分理论总结为“一个模型三个特征”。
1. 一个模型三个特征
一个模型指的是动态规划适合解决的问题的模型，我们把这个模型定义为“多阶段决策最优解模型”。我们一般是用动态规划来解决最优解问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。三个特征分别是最优子结构、无后效性和重复子问题。这三个概念比较抽象，下面逐一详细解释一下：
最优子结构是指，问题的最优解包含子问题的最优解。反过来说，我们可以通过子问题的最优解，推导出问题的最优解。对应到动态规划问题模型上就是，后面阶段的状态可以通过前面阶段的状态推导出来。
无后效性有两层含义：1）在推导后面阶段的状态时，我们只关心前面阶段的状态值，而不关心这个状态是怎么一步一步推导出来的。2）某阶段状态一旦确定，就不受之后阶段的决策影响。
重复子问题，用一句话概括一下就是，不同的决策序列在到达某个相同的阶段时可能会产生重复的状态。
一个模型三个特征这部分理论知识比较抽象，下面结合一个具体的动态规划问题来进行解释。假设我们有一个 nn 的矩阵 *w[n][n]，存储的都是正整数。我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？
这个问题是否符合“一个模型”？
如下图所示，从 (0, 0) 走到 (n-1, n-1)，总共要走 2(n-1) 步，也就对应着 2(n-1) 个阶段。每个阶段都有向右或向下走两种决策，并且每个阶段都会对应一个状态集合。同时我们求解的是最短路径长度。所以，这个问题是一个多阶段决策最优解问题，因此符合动态规划的模型。
这个问题是否符合“三个特征”？
如果我们画一下递归树，就会发现，递归树中有重复的节点。重复的节点表示，从左上角到节点对应的位置，有多种路线可达，因此符合“重复子问题”这一特征。
假设我们走到 (i, j) 这个位置，其中 i 表示行，j 表示列，则我们只能通过 (i-1, j)，(i, j-1) 移动过来。我们若要计算 (i, j) 的状态，只需关心 (i-1, j)，(i, j-1) 的状态**，而不关心棋子是通过怎样的路线到达这两个位置的。而且我们只允许往下和往右移动，不允许后退，所以，前面阶段的状态确定后，不会被后面阶段的决策所改变，因此符合“无后效性**”这一特征。
我们把从起始位置 (0, 0) 到 (i, j) 的最小路径，记作 min_dist(i, j)。到达 (i, j) 的最短路径要么经过 (i, j-1)，要么经过 (i-1, j)，而且到达 (i, j) 的最短路径肯定包含到达这两个位置的最短路径之一。因此，min_dist(i, j) 可以通过 min_dist(i, j-1) 和 min_dist(i-1, j) 两个状态推导出来。所以符合“最优子结构”这一特征。
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
2. 解题思路
解决动态规划问题，一般有两种思路。我把它们分别叫作，状态转移表法和状态转移方程法。
1.1 状态转移表法
一般能用动态规划解决的问题，都可以用回溯算法的暴力搜索来解决。我们可以先通过回溯算法，画出对应的递归树。从递归树中，查看是否存在重复子问题，以及重复子问题是如何产生的。以此来寻找规律，看是否能用动态规划来解决。找到重复子问题后，通常有两种处理思路，第一种是用回溯加备忘录的方法，来避免重复子问题。执行效率上和动态规划的解决思路没有差别。第二种就是使用状态转移表法。我们可以先画出一个状态表，一般是一个二维数组。其中，每个状态包含三个变量，行、列、数组值。我们根据决策的先后过程，从前往后递推，分阶段填充状态表中的每个状态。这个递推填表的过程就是动态规划的过程。
现在，我们来看下，如何套用这个状态转移表法，来解决上面那个矩阵最短路径的问题？首先，我们通过回溯算法的思想画出递归树，以此来寻找重复子问题。在递归树中，一个状态包含三个变量 (i, j, dist)，其中 i，j 分别表示行和列，dist 表示从起点到达 (i, j) 的路径长度。从图中可以看出，尽管 (i, j, dist) 不存在重复的，但 (i, j) 重复的有很多。对于 (i, j) 重复的节点，我们只需要选择 dist 最小的节点，继续递归求解，其他节点就可以舍弃了。
既然存在重复子问题，那是否可以用动态规划来解决呢？如下图所示，我们根据递归树画出对应的二维状态表，表中的行、列表示棋子所在的位置，表中的数值表示从起点到这个位置的最短路径。我们按照决策过程，通过不断状态递推演进，将状态表填好。为了方便代码实现，我们按行来进行依次填充。
代码实现
/** 4*4的矩阵 */
private static final int[][] chessboard = new int[4][4];
/** 状态数组，对应矩阵，数组值为从起始点到该节点的最短路径 */
private static final int[][] states = new int[4][4];
/**
* 求矩阵的最短路径
*/
public int minDist() {
// 初始化第一行
int sum = 0;
for (int i = 0; i < chessboard[0].length; i++) {
sum = sum + chessboard[0][i];
states[0][i] = sum;
}
// 初始化第一列
sum = 0;
for (int i = 0; i < chessboard.length; i++) {
sum = sum + chessboard[i][0];
states[i][0] = sum;
}
// 循环填充状态
for (int i = 1; i < chessboard[0].length; i++) {
for (int j = 1; j < chessboard.length; j++) {
// 取上一步路径短的节点来累加
states[i][j] = chessboard[i][j] + Math.min(states[i - 1][j], states[i][j - 1]);
}
}
return states[states.length - 1][states[0].length - 1];
}
这个例子也可以对应到 0-1 背包问题：
- 向右走还是向下走（装物品还是不装物品）
- 限制条件是路径总长度最短（限制条件是背包中总价值最高）
- 走下一步时，根据上一步中路径最短的节点来走（装物品时，根据上一次装物品时的状态来更新背包重量）
- 状态数组为：states[n][n]，值为路径长度（状态数组为：states[n][w+1]，值为物品价值）
1.2 状态转移方程法
状态转移方程法类似递归，即分析最优子结构。根据最优子结构写出递归公式，也就是所谓的状态转移方程。状态转移方程是解决动态规划的关键。如果能写出状态转移方程，那动态规划问题基就解决一大半了，再翻译成代码非常简单。一般有两种代码实现方法，一种是递归加备忘录，另一种是迭代递推。
/**
* 求矩阵的最短路径(递归+备忘录的方式实现)
*
* @param i 终点所在行
* @param j 终点所在列
*/
public static int minDist(int i, int j) {
if (i == 0 && j == 0) {
return chessboard[0][0];
}
// 如果备忘录里有数据，直接返回备忘录数据
if (mem[i][j] > 0) {
return mem[i][j];
}
// 从后一个节点倒推前一个节点，即状态转移方程
int minLeft = Integer.MAX_VALUE;
if (j - 1 >= 0) {
minLeft = minDist(i, j - 1);
}
int minUp = Integer.MAX_VALUE;
if (i - 1 >= 0) {
minUp = minDist(i - 1, j);
}
// 状态转移方程：min_dist(i,j)=chessboard[i][j] + min(min_dist(i-1,j), min_dist(i,j-1))
// 后一个节点是根据前一个节点走过来的
int currentDist = chessboard[i][j] + Math.min(minLeft, minUp);
mem[i][j] = currentDist;
return currentDist;
}
若有收获，就点个赞吧
0 人点赞
