动态规划的常见模型

所谓【模型】，就是将一类问题抽象成一个解题套路，然后根据这个套路来解题。

1️⃣ 0-1 背包问题

0-1 背包问题是一个基本问题，基于这个基本问题，可以衍生出千姿百态的变种问题，这种题目就非常适合拿来构造解题模型。

1.1 问题描述

有 n 件物品，物品体积用一个名为 w 的数组存起来，物品的价值用一个名为 value 的数组存起来；每件物品的体积用 w[i] 来表示，每件物品的价值用 value[i] 来表示。现在有一个容量为 c 的背包，问你如何选取物品放入背包，才能使得背包内的物品总价值最大？

注意：每种物品都只有 1 件

1.2 问题分析

我们遵循动态规划的解题思路，第一步，找到问题的某一状态，思考前进或后退的可能性。

如何定义这一状态？我们在动态规划的学习、解题过程中，总结出了一个小技巧：

单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。

这本质上是利用了动态规划的【最优子结构】特性，即：

一个问题的最优解可以由其子问题的最优解推导而来。

那么具体到 0-1 背包问题，问题是【考虑 1 ~ n 件物品，背包容量为 c，找出其价值最大的组合】。我们对前 i 个物品进行讨论，这不就是子问题吗？进一步地，我们定义子问题的最优解为 f(i, c)，注意这里的 i 是指对于前 i 个物品！

那么我们对编号为 i 的物品进行如下讨论：

1. 其不存在于最优解中：

   那么，我们完全可以将 i 排除出问题之外，不会有任何影响。此时问题就转化为了【考虑 1 ~ i - 1 件物品，背包容量为 c，找出其价值最大的组合】，其最优解显然为 f(i - 1, c);

   而由于将 i 排除后不会有任何影响，所以：f(i, c) === f(i - 1, c)

2. 其存在于最优解中：

   那么，如果我们将 i 从背包中拿出，会对背包的重量、价值均产生影响。此时问题转化为【考虑 1 ~ i - 1 件物品，背包容量为 c - w[i]，找出其价值最大的组合】，其最优解为 f(i - 1, c-w[i])；

   由于还会对价值产生影响，所以我们可以得出：f(i, c) - value[i] === f(i - 1, c - w[i])

这两种可能都需要考虑，而我们需要找最大，所以找这两者中的最大值即可：

f(i, c) = Math.max(f(i - 1, c), f(i - 1, c - w[i]) + value[i])

可以看到这里的子问题彼此之间是相互联系的，这就是动态规划的特性，它的子问题之间并不是独立的！

同时，这也是我们的状态转移方程。

接下来，第二步，确定迭代的方向和范围。

观察状态转移方程，自变量有两个：

1. i，即当前讨论物品中的最后一个物品编号（前 i 个物品！！！）
2. 当前背包容量，由于 c 是题目中明确指明的输入，所以这里用 v 来作为自变量标识符。

自变量明确了，接下来要确定范围：

• 对于 i，很明显，是从 1 迭代至 n；

• 对于当前背包容量，我们应该取一个什么范围呢？

  首先可以确定对于任意 i，背包容量不能是一个固定的值，其必须是变化的。

  其次，当我们讨论前 i 个物品时，背包容量至少要能够容纳下当前的物品 i，否则我们就没有讨论的必要了，因为其根本不可能在最优解中，而背包最大也不应该超过我们被给予的常量 c，所以背包容量应该是一个范围 [w[i], c]。

现在我们找到了迭代的方向和范围，如何将状态转移方程塞入迭代过程呢？这就是我们第三步要做的事了，找出基础状态，作为迭代的起点。

既然 f(i, v) 表示了考虑前 i 个物品，背包容量最大为 v 时的最大价值，那么当：

1. i === 0 时，显然，无论背包容量为多少，最大价值均为 0，因为还没有物品；
2. v === 0 时，显然，无论有多少个物品，最大价值均为 0，因为背包容量为 0；

所以，我们就可以将这两者作为基础状态，初始化 dp 数组，然后进行迭代。

// 这里 i 是物品数量，v 是背包容量，之所以背包容量是 v + 1，是因为要考虑背包容量为 0 的情况
const dp = new Array(i).fill(0).map(() => new Array(v + 1).fill(0));

接下来，第四步，将状态转移方程塞入迭代过程，进行迭代。

for (let i = 0;i < n;i++) {
    for (let v = w[i];v <= c; v++) {
        dp[i][v] = Math.max(dp[i - 1][v], dp[i -1][c - w[i]] + value[i])
    }
}

这里我们可以看到，当讨论不同背包容量的问题时，我们的背包容量是以 1 为单位逐渐增加的！

1.3 空间优化 - 滚动数组

现在，时间复杂度已经被我们优化到了 O(n) 的水平，相当不错。但是空间复杂度其实还可以再优化一下。不过不着急，初学背包问题，我们先站在巩固思路的角度，重现一下这个二维数组的填充过程：

从图中我们可以看出，计算 dp[i][v] 的时候，其实只需要图中标红位置的数据就可以了（这与前面讲解过的最优子结构特性不谋而合），也就是说未标红的地方对于 dp[i][v] 的计算来说都属于冗余数据。

实际上，对于第 i 行的计算来说，只有第 i-1 行的数据是有意义的，更早的数据它都不关心。也就是说我们其实根本不需要记录所有的数据，理论上只要保留当前行和上一行的数据就足够了。

所以，这里我们可以利用【滚动数组】的技巧，仅仅使用一位数组。

让我们重新看看状态转移方程和之前二维数组的填充过程

f(i, c) = Math.max(f(i - 1, c), f(i - 1, c - w[i]) + value[i])

可以看到，当我们计算 dp[i][v] 时，我们需要的是 dp[i-1][v-w[i]] 和 dp[i-1][v]，而 dp[i][v] 和 dp[i-1][v] 在二维数组的同一列上，那么我们能不能只用一行数组？记录 i - 1 行的数据，然后再计算 i 行时，从后往前计算，计算出 dp[i][v] 后将 dp[i-1][v] 覆盖掉，这样也不会影响后续的计算，也省了空间。

基于上面的分析，我们可以写出背包问题的完整求解代码：

// 入参是物品的个数和背包的容量上限，以及物品的重量和价值数组
function knapsack(n, c, w, value) {
  // 保存计算结果的数组，这里数组长度为 c + 1 因为要考虑背包容量为 0 的情况
  const dp = new Array(c + 1).fill(0);

  let res = -Infinity; // 结果

  for (let i = 0; i < n; i++) {
    for (let v = c; v >= w[i]; v--) {
      dp[v] = Math.max(dp[v], dp[v - w[i]] + value[i]);

      // 更新
      if (res < dp[v]) {
        res = dp[v];
      }
    }
  }

  return res;
}

2️⃣ 最长上升子序列问题

该模型对应的其实是动态规划中一类非常经典的问题 — 【序列型动态规划】。在形态各异的序列型动态规划问题中，“最长上升子序列”问题可以说是相当热门，其解法也是比较具有代表性的。接下来我们就以这个问题为抓手，提取其对应的的解题模型。

2.1 问题描述

题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n^2) 。

进阶: 能将算法的时间复杂度降低到 O(nlogn) 吗?

2.2 问题分析

在做这道题之前，首先要知道题目到底在说啥，这里的关键字有两个：【子序列】和【上升】。

【子序列】，它指的是在原有序列的基础上，删除0个或者多个数，其他数的顺序保持不变得到的结果。拿示例的这个序列来说：

[10,9,2,5,3,7,101,18]    

随便拿掉 0 个数或多个数：比如说我去掉第一个数字 10，去掉最后一个数 18，但是不打乱这个序列的顺序，那么我得到的新的序列就是该序列的一个子序列：

[9,2,5,3,7,101]    

而所谓【上升】，即排在后面的元素总是要大于排在前面的元素。

在之前的学习中，我们曾经了解过一种“通用解题思路”。通用解题思路的核心，是利用递归思想，以“倒推”为抓手，快速地明确状态与状态间的关系。当我们面对一道题目，无从下手的时候，这个思维工具往往能够帮到我们很大的忙。

然而，事事无绝对，学习动态规划并不是掌握一个套路就可以的。对于最长上升子序列问题来说，通用解题思路所描述的这种“自顶向下”的思维方式，并不好用。

事实上，做这道题，要把握住一个关键的特征，那就是【序列】。

这道题比较直白，直接把【序列】二字写在了题干里，而实际解题中更多的题目并不会明确指出它是【序列】类型题目，但是通过对题干进行分析，你会发现它实际上仍然会涉及到对一个序列的遍历，并且序列中的每一个元素都能够对应到一个有利于求解出最终结果的状态值（子问题的最优解！），这类题目也符合【序列】的特征。

对于序列类题目，我们并没有一套固定的解题模型可以直接套，一般来说只能见招拆招，针对不同的题型分支套不同的解法（所以确实需要有一定程度的题量上的积累）。解法虽有不同，背后的思想却是一而贯之的，那就是关注序列中元素的索引，尝试寻找不同索引对应的元素之间的关系、并以索引为线索去构造一维或二维的状态数组。

当然，动态规划类题目中，总还是有一些套路的：

单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。

所以，具体到这道题上来，第一步，找到子问题，定义状态，思考前进或后退的可能性。

我们定义 dp[i] 为考虑前 i 个元素，以第 i 个元素结尾的最长上升子序列的长度。接下来，尝试前进，若想基于 dp[i - 1] 求解出 dp[i]，我们需要关注到的是第 i 个元素和前 i - 1 个元素范围内的最长上升子序列的关系，它们之间的关系有两种可能：

1. 若第 i 个元素比前 i - 1 个元素中某一个元素要大，此时我们就可以在这个元素所在的上升子序列的末尾追加第 i 个元素（延长原有的子序列），得到一个新的上升子序列。
2. 若第 i 个元素并不比前 i - 1 个元素中所涵盖的最长上升子序列中的某一个元素大，则维持原状，子序列不延长。

所以，我们的状态转移方程为：

// 对于第 i 个元素来说，它需要遍历它前面的所有元素，看看能不能延长它们的最长上升子序列
for (let j = 0; j < i; j++) {
    if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)  
    }
}

接下来，第二步，确定迭代的方向和范围。

既然我们定义了 dp[i] 为考虑前 i 个元素，以第 i 个元素结尾的最长上升子序列的长度，由于第 1 个元素不需要讨论，dp[1] 必定为 1，那么我们的迭代方向自然就是从第 2 个元素开始，遍历到第 n 个元素结束。

然后，第三步，确定基础状态。

前面说过对于第 1 个元素来说，它本身就是一个长度为 1 的上升子序列，所以 dp[1] = 1。

而对于其他索引位来说，它们都与一个长度为 1 的子序列有关 — 那就是只有它自己存在的子序列。因此每一个索引位对应的状态初始值都是 1。

所以我们可以进行这样的初始化：

// 初始化数组里面每一个索引位的状态值
const dp = (new Array(nums.length)).fill(1);

最后，第四步，将状态转移方程塞入迭代过程，进行迭代。

2.3 图像分析

上面的分析过程有些许抽象，下面我们以题目示例中的数组 [10,9,2,5,3,7,101,18] 为例，通过图像的方式，来详细分析一下整个状态转移的过程。

在算法的初始态，我们还没有进行任何的遍历和计算，此时对于每一个索引位来说，它都只与一个长度为 1 的子序列有关 — 那就是只有它自己存在的子序列。因此每一个索引位对应的状态初始值都是 1：

同时对于索引位为 0 的元素来说，由于以它为结尾的子序列有且仅有 [10] 这一个，因此它的状态值时一开始就明确的，那就是 1：

dp[0] = 1

下面基于 dp[0] 对 dp[1] 求解，比较两个索引位上元素的大小：

发现 9 比 10 小，没办法延长原有的子序列，因此啥也不干。继续往下遍历，遇到了 2，发现 2 比前两个数都小，仍然没法延长任何一个子序列，继续啥也不干。

再往下遍历，遇到了 5，对比 5 和前面三个元素，发现它比 2 大，可以延长 2 所在的那个最长上升子序列，延长后，以 5 为结尾的最长上升子序列的长度就得到了更新：

重复上面这个【遍历新元素 + 回头看】的逻辑，直到整个数组被完全遍历，我们就能拿到以每一个索引位元素为结尾的最长上升子序列的长度值。从这些长度值中筛选出最大值，我们也就得到了问题的解。

2.4 代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
// 入参是一个数字序列
const lengthOfLIS = function(nums) {
  // 缓存序列的长度
  const len = nums.length;
  // 处理边界条件
  if(!len) {
      return 0;
  }
  // 初始化数组里面每一个索引位的状态值
  const dp = (new Array(len)).fill(1);
  // 初始化最大上升子序列的长度为1
  let maxLen = 1;
  // 从第2个元素开始，遍历整个数组
  for (let i = 1; i < len; i++) {
    // 每遍历一个新元素，都要“回头看”，看看能不能延长原有的上升子序列
    for (let j = 0; j < i; j++) {
      // 若遇到了一个比当前元素小的值，则意味着遇到了一个可以延长的上升子序列，故更新当前元素索引位对应的状态
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    // 及时更新上升子序列长度的最大值
    if (dp[i] > maxLen) {
      maxLen = dp[i];
    }
  }
  // 遍历完毕，最后到手的就是最大上升子序列的长度
  return maxLen;
};

3️⃣ 最长公共子序列模型

最长公共子序列问题属于经典的二维动态规划问题，我们的基本思路依然是先分析递归结构，然后【自底向上】递推。

写在前面，从这个模型中，我们可以得到一条解决二维字符串动态规划问题的基本经验 — 比较两个字符串的差异可以根据它们最后一个字符串的差异进行穷举。

3.1 问题描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

3.2 问题分析

第一步，找到子问题，定义状态，思考前进或后退的可能性。

仍然牢记：

单个数组或者字符串要用动态规划时，可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果；当两个数组或者字符串要用动态规划时，可以把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。

那么我们就假设字符串 text1 和 text2 的长度分别为 m 和 n，dp[i][j] 表示 text1[1:i] 和 text2[1:j] 的最长公共子序列的长度（注意下标从 1 开始）。

第二步，思考状态转移方程，根据 text1[i] 和 text2[j] 的情况，分为两种决策：

1. 若 text1[i] == text2[j]，也就是说两个字符串的最后一位相等，那么问题就转化成了字符串 text1 的 [1,j-1] 区间和字符串 text2 的 [1,j-1] 区间的最长公共子序列长度再加上 1，即 dp[i][j] = dp[i - 1][j - 1] + 1。（注意下标从 1 开始）

   

2. 若 text1[i] != text2[j]，也就是说两个字符串的最后一位不相等，那么字符串 text1 的 [1,i] 区间和字符串 text2 的 [1,j] 区间的最长公共子序列长度无法延长，因此 dp[i][j] 就会继承 dp[i-1][j] 与 dp[i][j-1] 中的较大值，即 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) 。 （注意下标从 1 开始）

   

由此，我们可以得到状态转移方程：

if (text1[i] === text2[j]) {
  dp[i][j] = dp[i - 1][j - 1];
} else {
  dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}

第三步，确定迭代的方向和范围。

显然，迭代的方向是自底向上，从 dp[0][0] 开始，一直到 dp[m][n] 结束。

第四步，确定基础状态。

空字符串与任意长度的字符串的最长公共子序列长度一定为 0，所以，我们可以将 dp[i][0] 和 dp[0][j] 都置为 0。同时，注意这题里要提前把溢出情况比如 dp[-1][0]、dp[-1][-1] 考虑进去，防止访问时报错，比如在求解 dp[0][0] 并且两个字符串的第 0 位都相同的时候就会转而去求 dp[-1][-1]，这里我们可以将 dp 数组在两个维度都多扩展一位，这样就不会出现溢出的情况了。

所以我们可以进行如下的初始化：

let dp = []

for (let i1 = 0; i1 <= text1.length; i1++) {
    dp[i1] = []
    dp[i1][0] = 0
}
dp[0] = Array(text2.length + 1).fill(0)

最后，第五步，将状态转移方程塞入迭代过程，进行迭代。

/**
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
let longestCommonSubsequence = function (text1, text2) {
    let n1 = text1.length
    let n2 = text2.length

    let dp = []

    for (let i1 = 0; i1 <= n1; i1++) {
        dp[i1] = []
        dp[i1][0] = 0
    }
    dp[0] = Array(n2 + 1).fill(0)

    for (let i1 = 1; i1 <= n1; i1++) {
        for (let i2 = 1; i2 <= n2; i2++) {
            let str1 = text1[i1 - 1]
            let str2 = text2[i2 - 1]

            if (str1 === str2) {
                dp[i1][i2] = 1 + dp[i1 - 1][i2 - 1]
            }else {
                dp[i1][i2] = Math.max(dp[i1 - 1][i2], dp[i1][i2 - 1])
            }
        }
    }

    return dp[n1][n2]
};

为什么这道题可以作为模型来学习？因为其中包含了两个基本的【解题套路】：

• 对于二维字符串动态规划问题，我们可以通过对两者最后一位字符的差异进行穷举来找到状态之间的转移关系；
• 对于二维动态规划问题，我们常常把动态规划定义成两维的 dp[i][j] ，其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。