动态规划

[Leo-lin214]

借用一个比较典型的生活例子：

有一天，有个爸爸想考一下儿子的数学，就问“儿子，1 + 1 = ?”。

“好简单啊，就是2”。

“好，如果我让你在原来那个式子前面补上 1 +，结果是多少呢？”。

“原来的式子 1 + 1 = 2，那么左边再补上 1 +，就相当于 1 + 2，结果就是3”。

动态规划的定义就是把一个大问题拆解成一个或多个小问题进行求解。

按照定义，我们可以将上面的例子进行转换一下，已知2个1的结果是2，那么3个1的结果会是多少？显然易见，大问题就是3个1，那么我们可以将它拆解一下，就可以得到3个1的结果 = 2个1的结果 + 1，以此类推，我们只需要知道中间的某个计算值即可得到最终大问题的结果。

那么，你会发现里面会存在一个动态规划的关键点，那就是每个小问题的解都会被存储起来，重复调用结果后从而得到大问题的解。

也许上面的例子看的不是很明显，再举一个例子：

有 N 个阶梯，一个人每一步只能跨一个台阶或者两个台阶，那么到达 N 个阶梯后总共有多少种跨法？

从题目我们可以分析一下：

• 大问题：N个阶梯的跨法。
• 拆解小问题：N - 1 个阶梯再走一步就可以到 N 个阶梯，N - 2 个阶梯再走两步就可以到达 N 个阶梯。

因此，我们很容易得到大问题和小问题之间关系：N个阶梯跨法 = (N - 1 个阶梯跨法 + 1) + (N - 2 个阶梯跨法 + 2)。

而大问题和小问题之间的关系恰好就是所谓的状态转移方程。

这样一来，我们就可以通过代码来实现 N 个阶梯的跨法：

const getResult = n => {
  if (!n) return 0;
  const result = [];
  result[0] = 1;
  result[1] = 1;
  for (let i = 2; i <= n; i++) {
    result[i] = result[i - 1] + result[i - 2];
  }
  return result[n];
}

你会发现，N 个台阶最终都会重复调用 N - 1个台阶和 N - 2 个台阶结果，这也正是上面将每个小问题的结果存储起来重复调用后得到最终大问题的解。

原理大概有所了解了，那么我们就继续看看其他例子深入理解一下。

斐波那契数列

0、1、1、2、3、5、....，求第 N 个数是多少？

从题目分析一下：

• 大问题：第 N 个数的结果。
• 拆解小问题：第 N 个数刚好就是第 N - 1 个数和第 N - 2 个数的和。

因此，我们可以很容易得到状态转移方程：第 N 个数 = (第 N - 1 个数) + (第 N - 2 个数)。

代码实现如下：

const getResult = n => {
  const result = [];
  result[0] = 0;
  result[1] = 1;
  for (let i = 2; i <= n; i++) {
    result[n] = result[n - 1] + result[n - 2];
  }
  return result[n];
}

钢条切割问题

某公司出售钢条，出售的价格与钢条长度之间的关系如下：

长度 i	1	2	3	4	5	6	7	8	9	10
价格 pi	1	5	8	9	10	17	17	20	24	30

现有一段长度为 N 的钢条和上面的价格表，求切割钢条方案，使得总收益最大。

从问题进行分析：

• 大问题：长度为 N 的钢条的最大收益。
• 拆解小问题：
  • 当 N 小于 10，那么最大收益就可以为 Max(n) = Math.max(p[n], p[n - 1] + Max(n - n - 1), p[n - 2] + Max(n - n - 2), ..., p[n] + Max(0))。
  • 当 N 大于 10，那么最大收益就可以为 Max(n) = Math.max(Max(n - 1) + Max(1), Max(n - 2) + Max(2), ..., Max(1) + Max(n - 1))。

代码实现如下：

const getResult = n => {
  const price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30];
  const result = [0, 1];
  for (let i = 2; i <= n; i++) {
    result[i] = 0;
    const mid = parseInt((i - 1) / 2) + 1;
    for (let j = i; j >= mid; j--) {
      const temp = i <= 10 ? price[j] : result[j];
      result[i] = Math.max(temp + result[i - j], result[i]);
    }
  }
  return result[n];
}

最长公共子序列（LCS）

一个序列的子序列定义为：在该序列中删去若干元素后得到的序列，如 “ABCD” 和 “BDF” 都是 “ABCDEFG” 的子序列。

最长公共子序列问题：给定两个序列 X 和 Y，求 X 和 Y 长度最大的公共子序列。

举例：X = “ABBCBDE”，Y = “DBBCDB”，LCS(X, Y) = “BBCD”。

从题目进行拆解分析：

• 大问题： 两个字符串的最长公共子序列，抽象为两个字符是否相等。
• 拆解小问题：
  • 当 X 和 Y 两个字符相等时，那么 Result(X, Y) = Result(X - 1, Y - 1) + 1。
  • 当 X 和 Y 两个字符不相等时，那么 Result(X, Y) = Math.max(Result(X - 1, Y), Result(X, Y - 1))。

代码实现如下：

const getResult = (str1, str2) => {
  if (!str1 || !str2) return "";
  const arr1 = str1.split('');
  const arr2 = str2.split('');
  const result = [];
  for (let i = 0; i <= arr1.length; i++) {
    result[i] = [];
    for (let j = 0; j <= arr2.length; j++) {
      if (i === 0) {
        result[i][j] = "";
      } else if (j === 0) {
        result[i][j] = "";
      } else if (arr1[i - 1] === arr2[j - 1]) {
        result[i][j] = result[i - 1][j - 1] + arr1[i - 1];
      } else {
        result[i][j] = result[i - 1][j] > result[i][j - 1] ? result[i - 1][j] : result[i][j - 1];
      }
    }
  }
  return result[arr1.length][arr2.length];
}