动态规划

使用递归解决问题虽然简洁，但效率不高。包括 JavaScript 在内的众多语言，不能高效地将递归代码解释为机器代码，尽管写出来的程序简洁，但是执行效率低下。但这并不是说使用递归是件坏事，本质上说，只是那些指令式编程语言和面向对象的编程语言对递归的实现不够完善，因为它们没有将递归作为高级编程的特性。

许多使用递归去解决的问题，可以重写为使用动态规划的技巧解决。动态规划方案通常会用一个数组去建立一张表，用于存放被分解成众多子问题的解。当算法执行完毕，最终的解将会在这个表中很明显的地方被找到。

动态规划实例：计算斐波那契数列

斐波那契数列可以定义为一下序列：

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

可以看到，该序列是由前两项数值相加而成。这个数列的历史非常悠久，至少可以追溯到公元 700 年。它以意大利亚数学家 列奥纳多·斐波那契的名字命名，斐波那契在 1202 年使用这个数列描述理想状态下兔子的增长。

这个是一个简单的递归函数，可以使用它来生成数列中指定序号的数值。

function recurFib() {
  if (n > 2) {
    return n
  } else {
    return recurFib(n - 1) + recurFib(n - 2)
  }
}

这个函数的问题在于它的执行效率非常低。原因在于递归中有太多的值被重复计算。看下图计算 fib(5) 的过程：

**

如果能够将已经计算的值记录下来，函数的执行效率将大大提高。我们可以使用动态规划的技巧来设计一个效率更高的算法。

使用动态规划设计的算法从它能解决的最简单的子问题开始，继而通过得到的解，去解决其他更复杂的子问题，直到整个问题都被解决。所有子问题的解通常会被存储在一个数组里以便访问。
**
我们可以通过研究使用动态规划的技巧来计算斐波那契数列来展示动态规划的本质：

function dynFib(n) {
  if (n < 2) return n
  let val = []
  val[0] = 0
  val[1] = 1
  for (let i = 2; i <= n; i++) {
    val[i] = val[i - 1] + val[i - 2]
  }
  return val[n]
}

在测试其速度时，动态规划明显比递归快很多。

实际上，在使用迭代方案计算斐波那契数列时，可以不使用数组进行存储。需要用到数组的原因是因为动态规划算法通常需要将中间结果保存起来。

function iterFib(n) {
  if (n < 2) return n
  let last = 1
  let nextLast = 1
  let result = 1
  for (let i = 2; i < n; i++) {
    result = last + nextLast
    nextLast = last
    last = result
  }
  return result
}

寻找最长公共子串

另一个适合使用动态规划去解决的问题是寻找两个字符串的最长公共子串。例如：在单词 raven 和 havoc 中，最长公共子串是 av。寻找最长公共子串常用于遗传学中，用于使用核苷酸中碱基的首字母对 DNA 分子进行描述。

我们从暴力方式开始去解决这个问题。给出两个字符串 A 和 B，我们可以通过从 A 的第一个字符开始与 B 的对应第一个字符进行比对的方式找到他们的最长公共子串。如果此时没有找到匹配的字母，则移动到 A 的第二个字母处，然后从 B 的第一个字符处进行比对，以此类推。

动态规划是更适合解决这个问题的方案。这个算法使用一个二维数组存储两个字符串相应位置的字符比较结果。初始化时，该数组的每一个元素被设置为 0。每次在这两个数组的相同位置发现了匹配，就将数组对应行和列的元素加 1，否则保持为 0。

按照这种方式，一个变量会持续记录下找到了多少个匹配项。当算法执行完毕时，这个变量会结合一个索引变量来获得最长公共子串。

function lcs(str1, str2) {
  let max = 0
  let index = 0
  // 初始化二维数组
  let lcsArr = new Array(str1.length + 1)
  for (let i = 0; i <= str1.length; i++) {
    lcsArr[i] = new Array(str2.length + 1)
    for (let j = 0; j < str2.length; j++) {
      lcsArr[i][j] = 0
    }
  }
  // 构建用于保存字符串匹配记录的表
  for (let i = 0; i <= str1.length; i++) {
    for (let j = 0; j <= str2.length; j++) {
      if (i === 0 || j === 0) {
        lcsArr[i][j] = 0;
      } else {
        if (str1[i - 1] === str2[j - 1]) {
          lcsArr[i][j] = lcsArr[i - 1][j - 1] + 1
        } else {
          lcsArr[i][j] = 0
        }
      }
      if (max < lcsArr[i][j]) {
        max = lcsArr[i][j]
        index = i
      }
    }
  }
  // 确定从哪里开始构建最长公共子串
  let str = ''
  if (max === 0) return ""
  for (let i = index - max; i <= index; i++) {
    str += str1[i]
  }
  return str
}

分为三个部分：

（1）第一部分初始化了两个变量以及一个二维数组。

（2）第二部分构建了用于保存字符匹配记录的表。数组的第一个元素总是被设置为 0.如果两个字符串相应位置的字符进行匹配，当前数组元素的值将被设置为前一次循环中数组元素保存的值加 1。如果当前变量 max 的值比现在存储在数组中当前元素的值要小，max 的值将被赋值为这个元素，变量 index 的值将被设置为 i 的当前值。

如：’abbcc’、’dbbcc’ 构建的表为：

（3）第三部分用于确认从哪里开始构建这个字符串。由于 index 变量存储的是 i 值，即第一个字符串的值，那么最长子串就是第一个字符串从下标 index - max 开始到 index 范围的字符串。

背包问题

背包问题是算法研究中的一个景点问题。在有限的容量中取得最大的价值：保险箱中有五件物品，尺寸分别是 3、4、7、8、9，而它们的价值分别是 4、5、10、11、13，但是背包容量只有 16，那么最恰当的方案是选取哪些物品？

递归解决方案

function max(a, b) {
  return a > b ? a : b
}
function recurPackage(content, sizes, values, n) {
  if (n === 0 || content === 0) return 0
  if (sizes[n - 1] > content) {
    return recurPackage(content, sizes, values, n - 1)
  } else {
    return max(
      values[n - 1] + recurPackage(content - sizes[n - 1], sizes, values, n - 1),
      recurPackage(content, sizes, values, n - 1))
  }
}

其核心思想是：每一次都会有两种选择，经过不断的细分，最终会尝试每一种可能，而每一个小结果中，只取最大值，最后返回的也就是最大值。

动态规划解决方案

使用递归方案能解决的问题，都能够使用动态规划技巧来解决，而且能够提高程序的执行效率。

背包问题使用动态规划方案来解决，要做的只是使用一个数组来保存临时解，直到获得最终的解为止。

function dynPackage(content, sizes, values, n) {
  let k = []
  for (let i = 0; i <= n + 1; i++) {
    k[i] = []
  }

  for (let i = 0; i <= n; i++) {
    for (let j = 0; j <= content; j++) {
      if (i === 0 || j === 0) {
        k[i][j] = 0
      } else if (sizes[i - 1] <= j) {
        k[i][j] = max(values[i - 1] + k[i - 1][j - sizes[i - 1]], k[i - 1][j])
      } else {
        k[i][j] = k[i - 1][j]
      }
    }
    console.log(k[i]);
  }
  return k[n][content]
}

动态规划的方案基本上都会构建一个二维表格，在不断的循环解决小问题的过程中，得到最优解。

上面就是最终的二维数组 k 的值