动态规划（DP）
简介 #
动态规划（DP）是打表的最高境界. 我们从一个案例入手 DP.
案例 #
斐波那契数列形如 $\{1,1,2,3,5,8,\cdots\}$. 计算此数列的第 $n$ 项 $f[n]$.
根据数列特征，列出递推公式
$$f[n]= \begin{cases} 1&n=1,2\\ f[n-1]+f[n-2]&n\geq 3 \end{cases}$$
首先，将 $f[1]=1,f[2]=1$ 填入表.
| $f[1]$ | $f[2]$ |
|---|---|
| $1$ | $1$ |
计算 $f[3]=f[2]+f[1]$ 并填入表.
| $f[1]$ | $f[2]$ | $\color{red}{f[3]}$ |
|---|---|---|
| $1$ | $1$ | $\color{red}{2}$ |
计算 $f[4]=f[3]+f[2]$ 并填入表.
| $f[1]$ | $f[2]$ | $f[3]$ | $\color{red}{f[4]}$ |
|---|---|---|---|
| $1$ | $1$ | $2$ | $\color{red}{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[n]= \begin{cases} 1&n=1,2\\ f[n-1]+f[n-2]&n\geq 3 \end{cases}$$