动态规划

动态规划（Dynamic Programming，DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

Programming 指的是一种表格法

基本思想

动态规划算法通常用于求解满足 最优子结构（optimal substructure） 的问题：问题的最优解由相关子问题的最优解组合而成。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。

若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。 通过缓存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

即，空间换时间

不管子问题以后是否被用到，只要它被计算过，就将其缓存。

分类

动态规划一般分为：

• 线性动规

• 区域动规

• 树形动规

• 背包动规

动态规划的应用

四个步骤采用动态规划解决问题：

1. 刻画一个最优解的结构特征。

2. 递归地定义最优解的值

3. 计算最优解的值，通常采用自底向上的方法

4. 利用计算出的信息构造一个最优解

使用动态规划动重点在于列出问题的状态转移方程。

斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列。

F(1)=1
F(2)=1
F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

使用递归求斐波那契数列：

function fibonacci(n) {
  if (n <= 2) {
    return 1;
  }

  return fibonacci(n - 1) + fibonacci(n - 2);
}

采用自底向上的动态规划求解：

function fibonacci(n) {
  const dp = [1, 1]; // f(1), f(2)

  for (let i = 2; i < n; ++i) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n - 1];
}

钢条切割问题

参考

五大基本算法之动态规划算法 DP