动态规划算法

动态规划是一种计算机编程方法，通过将一个大的问题，递归的分解成子问题，然后对每个子问题应用同样的解决方案，经过组合得到大问题的答案。动态规划必须要满足两个特定的条件：

重叠子问题指的是，子问题的答案，会在其他子问题中重复用到，动态规划会保存子问题的答案来避免重复计算。最优子结构指的是给定的大问题的最优答案可以通过合并子问题的最答案来获得。

动态规划的解法有两种：

自顶向下递归的从大问题开始，逐一计算子问题，并把子问题的结果保存起来，后面如果再用到相同子问题的结果，则直接从保存的结果中获取。自底向上与自顶向下的方式相反，先从最小的子问题计算，同时也保存计算结果，直到计算到大问题本身，得到最终答案。

我们来看一个最简单的例子，计算斐波那契数列，如果使用递归的方式实现，需要重复计算很多次：

javascript

function fib(n) {
  if (n <= 1) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

这样，即使指定 n 为一个较小的数字，也会需要很长的时间才能计算完成。这个时候，如果我们通过一个数组，把之前计算的结果保存起来，这样就省去了所有的重复计算，直接拿前边两个计算结果进行相加就可以了：

javascript

function fib(n) {
  const fib = [0, 1];
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  return fib[n];
}

算法执行效率会大大提高。这样就利用到了动态规划，这个示例是自底向上的方式来解决的，即从 0 开始一直计算到 n，如果采用自顶向下则从 n 计算到 0，这里就不演示了。

要注意的是，并不是所有的递归算法都能用动态规划来优化，例如归并排序，因为它的子问题没有重叠之处，对每个子数组都要进行排序，所以它的这种解法叫做分治，而不是动态规划。

动态规划可以解决有下面这些描述的问题：

动态规划算法 ​