动态规划

动态规划背后的基本思想非常简单。就是将一个问题拆分为子问题，一般来说这些子问题都是非常相似的，那么我们可以通过只解决一次每个子问题来达到减少计算量的目的。

一旦得出每个子问题的解，就存储该结果以便下次使用。

斐波那契数列

斐波那契数列就是从 0 和 1 开始，后面的数都是前两个数之和

0，1，1，2，3，5，8，13，21，34，55，89….

那么显然易见，我们可以通过递归的方式来完成求解斐波那契数列

  1. function fib(n) {
  2.   if (n < 2 && n >= 0) return n
  3.   return fib(n - 1) + fib(n - 2)
  4. }
  5. fib(10)

以上代码已经可以完美的解决问题。但是以上解法却存在很严重的性能问题，当 n 越大的时候，需要的时间是指数增长的，这时候就可以通过动态规划来解决这个问题。

动态规划的本质其实就是两点

  1. 自底向上分解子问题
  2. 通过变量存储已经计算过的解

根据上面两点，我们的斐波那契数列的动态规划思路也就出来了

  1. 斐波那契数列从 0 和 1 开始，那么这就是这个子问题的最底层
  2. 通过数组来存储每一位所对应的斐波那契数列的值
  1. function fib(n) {
  2.   let array = new Array(n + 1).fill(null)
  3.   array[0] = 0
  4.   array[1] = 1
  5.   for (let i = 2; i <= n; i++) {
  6.     array[i] = array[i - 1] + array[i - 2]
  7.   }
  8.   return array[n]
  9. }
  10. fib(10)

0 - 1背包问题

该问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。每个问题只能放入至多一次。

假设我们有以下物品

物品 ID / 重量 价值
1 3
2 7
3 12

对于一个总容量为 5 的背包来说，我们可以放入重量 2 和 3 的物品来达到背包内的物品总价值最高。

对于这个问题来说，子问题就两个，分别是放物品和不放物品，可以通过以下表格来理解子问题

物品 ID / 剩余容量 0 1 2 3 4 5
1 0 3 3 3 3 3
2 0 3 7 10 10 10
3 0 3 7 12 15 19

直接来分析能放三种物品的情况，也就是最后一行

  • 当容量少于 3 时，只取上一行对应的数据，因为当前容量不能容纳物品 3
  • 当容量 为 3 时，考虑两种情况，分别为放入物品 3 和不放物品 3
    • 不放物品 3 的情况下，总价值为 10
    • 放入物品 3 的情况下，总价值为 12，所以应该放入物品 3
  • 当容量 为 4 时，考虑两种情况，分别为放入物品 3 和不放物品 3
    • 不放物品 3 的情况下，总价值为 10
    • 放入物品 3 的情况下，和放入物品 1 的价值相加，得出总价值为 15，所以应该放入物品 3
  • 当容量 为 5 时，考虑两种情况，分别为放入物品 3 和不放物品 3
    • 不放物品 3 的情况下，总价值为 10
    • 放入物品 3 的情况下，和放入物品 2 的价值相加，得出总价值为 19，所以应该放入物品 3

以下代码对照上表更容易理解

  1. /**
  2.  * @param {*} w 物品重量
  3.  * @param {*} v 物品价值
  4.  * @param {*} C 总容量
  5.  * @returns
  6.  */
  7. function knapsack(w, v, C) {
  8.   let length = w.length
  9.   if (length === 0) return 0
  11.   // 对照表格，生成的二维数组，第一维代表物品，第二维代表背包剩余容量
  12.   // 第二维中的元素代表背包物品总价值
  13.   let array = new Array(length).fill(new Array(C + 1).fill(null))
  15.   // 完成底部子问题的解
  16.   for (let i = 0; i <= C; i++) {
  17.     // 对照表格第一行， array[0] 代表物品 1
  18.     // i 代表剩余总容量
  19.     // 当剩余总容量大于物品 1 的重量时，记录下背包物品总价值，否则价值为 0
  20.     array[0][i] = i >= w[0] ? v[0] : 0
  21.   }
  23.   // 自底向上开始解决子问题，从物品 2 开始
  24.   for (let i = 1; i < length; i++) {
  25.     for (let j = 0; j <= C; j++) {
  26.       // 这里求解子问题，分别为不放当前物品和放当前物品
  27.       // 先求不放当前物品的背包总价值，这里的值也就是对应表格中上一行对应的值
  28.       array[i][j] = array[i - 1][j]
  29.       // 判断当前剩余容量是否可以放入当前物品
  30.       if (j >= w[i]) {
  31.         // 可以放入的话，就比大小
  32.         // 放入当前物品和不放入当前物品，哪个背包总价值大
  33.         array[i][j] = Math.max(array[i][j], v[i] + array[i - 1][j - w[i]])
  34.       }
  35.     }
  36.   }
  37.   return array[length - 1][C]
  38. }

最长递增子序列

最长递增子序列意思是在一组数字中，找出最长一串递增的数字，比如

0, 3, 4, 17, 2, 8, 6, 10

对于以上这串数字来说，最长递增子序列就是 0, 3, 4, 8, 10，可以通过以下表格更清晰的理解

数字 0 3 4 17 2 8 6 10
长度 1 2 3 4 2 4 4 5

通过以上表格可以很清晰的发现一个规律，找出刚好比当前数字小的数，并且在小的数组成的长度基础上加一。

这个问题的动态思路解法很简单，直接上代码

  1. function lis(n) {
  2.   if (n.length === 0) return 0
  3.   // 创建一个和参数相同大小的数组，并填充值为 1
  4.   let array = new Array(n.length).fill(1)
  5.   // 从索引 1 开始遍历，因为数组已经所有都填充为 1 了
  6.   for (let i = 1; i < n.length; i++) {
  7.     // 从索引 0 遍历到 i
  8.     // 判断索引 i 上的值是否大于之前的值
  9.     for (let j = 0; j < i; j++) {
  10.       if (n[i] > n[j]) {
  11.         array[i] = Math.max(array[i], 1 + array[j])
  12.       }
  13.     }
  14.   }
  15.   let res = 1
  16.   for (let i = 0; i < array.length; i++) {
  17.     res = Math.max(res, array[i])
  18.   }
  19.   return res
  20. }