动态规划 - wangshengliang

常见的算法思维：

分治法
迭代法
枚举法
回溯法
贪心法
动态规划

动态规划，英语叫做 Dynamic Programming，简称 DP，这是一种解决复杂问题的方法，其最最最核心的思想，就是 将问题分解成子问题，只要子问题解决了，那么这个复杂问题也就解决了。

和分治法的区别：
核心区别在于子问题是否存在重叠性，相同的子问题可能会被多次计算，动态规划通过存储子问题的结果（记忆化搜索或自底向上计算）来避免重复计算。相比之下，分治法通常将问题拆分成相互独立的子问题，然后合并子问题的结果。

DP 核心特点#

最优子结构（Optimal Substructure）
重叠子问题（Overlapping Subproblems）
存储子问题的解（Memoization / Tabulation）

1. 最优子结构#

最优子结构指的是：某个问题的最优解可以通过其子问题的最优解来构造。换句话说，假如你想求问题 P 的最佳答案，那么可以先把 P 拆分为若干子问题 P₁、P₂、P₃、P₄ … ，并把它们分别求出这些子问题的最优解，然后再根据子问题的最优解组合出 P 的最优解。

实际上，拥有最优子结构是许多算法设计策略（包括分治法、贪心算法、动态规划）的一个重要前提。对于 DP 来说，没有最优子结构就无法通过拆分子问题来推导原问题的解。

一个实际的例子：斐波那契数列

计算斐波那契数列的第 n 项，这里就需要拆解成 n-1 项和 n-2 项，然后得到这两个子问题的最优解，最终能够组合得到第 n 项的最优解。

2. 重叠子问题#

重叠子问题指的是：在将原问题分解为若干子问题后，这些子问题在问题的求解过程中会重复出现，从而导致你重复的计算多次。

分治法虽然也会把问题拆分成子问题，但在很多分治问题里，这些子问题要么不重叠，要么仅仅少量重叠；而动态规划则通常在大规模、带有递推性质的场景中，大量重复的子问题被反复计算。如果不加以记录，就会做许多 重复计算，从而影响效率。

一个例子：斐波那契数列

F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
- F(3) = F(2) + F(1)
F(3) = F(2) + F(1)

3. 存储子问题的解#

对于不断重叠出现的子问题，如果我们能把它们的解存储起来，下次遇到相同的子问题就直接取结果，而不是重新计算，便能大大降低算法的时间复杂度。

在实现层面，通常有两种形式：

记忆化搜索（Memoization，Top-Down）自上而下
表格法（Tabulation，Bottom-Up）自下而上

存储子问题解这一特性让动态规划和纯粹的分治算法区分开来，也显著地提高了运算效率。纯分治往往不刻意缓存子问题结果，而是“算完就走”，需要时再重新计算；而 DP 会把结果记下来，这就是动态规划“动态”这个概念体现的地方：我们可以说状态是“动态地”沿着子问题规模的增加而得到维护和更新。

状态转移方程#

状态转移方程 就是描述 从一个状态如何过渡到另一个状态 的规则或公式。它本质上是一种 递推/递归关系，用来指导我们如何从小规模子问题的解，一步步累积得到大规模问题的解。

换句话说：一个问题的解可以由它的子问题解来合成。“状态转移方程”就把这种合成过程用正式的数学或伪代码表达出来。

例如斐波那契数列可以写成：

F(n)=F(n−1)+F(n−2)，F(0)=0,F(1)=1

而在背包问题中的，若令 dp[i][c] 表示在只考虑前 i 个物品、容量为 c 的情况下能达到的最大价值，那么状态转移方程就可以写成：

dp[i][c] = \max\Bigl( dp[i-1][c],\, dp[i-1][c - \text{weight}_i] + \text{value}_i \Bigr)

一般来讲，DP 的题目中状态转移方程列举出来了，题目基本上就完成一半了。

那么如何来列出这个重要的状态转移方程呢？多练题

具体实践#

题目#

斐波那契数列（Fibonacci Sequence）指的是这样一个数列：

F(0)=0
F(1)=1
从第二项开始，每一项都等于前两项之和，即：

F(n)=F(n−1)+F(n−2)，n≥2

**要求：**给定一个整数 n，请你计算 F(n) 并返回结果。

举例：

当 n=0 时，F(0)=0
当 n=1 时，F(1)=1
当 n=5 时，F(5)=5（序列为 0, 1, 1, 2, 3, 5, 8, 13, 21…）

解题思路#

最基础、最直观的思路是递归：F(n) = F(n-1) + F(n-2)。但如果我们直接用“自顶向下”的纯递归算法，会有大量重复计算。例如，计算 F(5) 时，需要先算 F(4) + F(3)；计算 F(4) 又要算 F(3) + F(2)……很多重复。“动态规划”能通过 存储子问题解 来避免重复计算，将原本指数级复杂度降低到线性或更优。

最优子结构

最优子结构指的是：原问题的最优解可以由其子问题的最优解组合而成。

对于斐波那契数列，F(n) = F(n-1) + F(n-2) 正说明了：要想得到 F(n)，只需要先把 F(n-1) 和 F(n-2) 计算好（它们各自都是各自子问题的“最优解”——对于数列而言，就是唯一且正确的值），然后将这两个结果相加即可。

重叠子问题

斐波那契数列的子问题有大量重叠：

比如纯递归计算 F(5) 时：
- F(5) 会调用 F(4) 和 F(3)
- F(4) 会调用 F(3) 和 F(2)
- 可以看到，F(3) 被反复调用了多次，这就是子问题重叠。

存储子问题的解

在动态规划中，通过存储已经算好的子问题 F(k) 的值，下次再需要时就直接取用，不必再次计算。

实现方式上，可以记忆化搜索（Memoization） 或 表格法（Tabulation）。对斐波那契来说，表格法相对来讲会更简单，开一个数组 dp，其中 dp[i] 用来存储 F(i)。

状态转移方程

斐波那契数列之所以适合作为动态规划的入门题，就是因为题目中已经将状态转移方程告诉你了。

状态定义：用 dp[i] 来表示 F(i) 的值，即斐波那契数列第 i 项。
状态转移方程：
$dp[i]=dp[i−1]+dp[i−2]$
初始条件：
$dp[0]=0,dp[1]=1$
计算顺序：当我们用“表格法”解斐波那契时，可以从 i = 2 往后依次计算，直至 i = n，这样前面的 dp[0], dp[1]... dp[i-1]、dp[i-2] 都已经就绪，可用于计算下一步。

代码实现

使用表格法（自下而上）

/**
 * n - 斐波那契的第 n 项
 */
function fibonacci(n) {
  if (n < 2) {
    return n
  }

  // 接下来我们需要一个 dp 数组来记录状态
  const dp = new Array(n + 1)

  // 接下来做初始化
  dp[0] = 0
  dp[1] = 1

  for (let i = 2; i <= n; i++) {
    // 填充表格
    dp[i] = dp[i - 1] + dp[i - 2]
  }

  return dp[n]
}

-EOF-