案例

我们从一个案例入手 DP。

EXAMPLE

斐波那契数列又称黄金分割数列，其数值为

$$\{1,1,2,3,5,8,\cdots \}$$

其中每一项都等于前两项之和。计算该数列的第 $n$ 项 $f[n]$。

根据数列的特征，容易列出递推公式：

$$f[n]=\{\begin{array}{ll}1& n=1,2\\ f[n-1]+f[n-2]& n\ge 3\end{array}$$

首先，将 $f[1]=1,f[2]=1$ 填入表。

$f[1]$	$f[2]$
$1$	$1$

计算 $f[3]=f[2]+f[1]$ 并填入表。

$f[1]$	$f[2]$	$f[3]$
$1$	$1$	$2$

计算 $f[4]=f[3]+f[2]$ 并填入表。

$f[1]$	$f[2]$	$f[3]$	$f[4]$
$1$	$1$	$2$	$3$

重复计算填表的步骤，直到得到 $f[n]$。

$f[1]$	$f[2]$	$f[3]$	$f[4]$	$f[5]$	$f[6]$	$f[7]$	$\cdots$	$f[n]$
$1$	$1$	$2$	$3$	$5$	$8$	$13$	$\cdots$

时间复杂度：$O(n)$。

f[1] = f[2] = 1;
for (int i = 3; i <= n; i ++)
	f[i] = f[i - 1] + f[i - 2];

术语

状态

状态是表格中所填数字的意义。

案例 的状态 $f[i]$ 定义为斐波那契数列的第 $i$ 项。

状态转移方程

描述状态间关系的方程。

案例 的状态转移方程为

$$f[n]=f[n-1]+f[n-2]$$

边界条件

一开始就知道的状态。

案例 的边界条件为

$$f[1]=1,f[2]=1$$

DP 步骤

1. 为问题设计 状态；
2. 列出 状态转移方程；
3. 从 边界条件 开始，以 正确的顺序 求解所有状态。

递推和 DP 的区别

DP 很多时候和递推很像，但二者的概念不同。

具体来说，DP 有多种实现方式，而递推是其中一种。

• 当状态的计算顺序容易确定时，通常采用递推（如 案例 中采用线性顺序）；
• 当状态的计算顺序难以确定时，通常采用 记忆化搜索。