Skip to content

动态规划

2021-01-15

动态规划是打表的最高境界。

案例

我们从一个案例入手 DP。

EXAMPLE

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

{1,1,2,3,5,8,}

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

根据数列的特征,容易列出递推公式:

f[n]={1n=1,2f[n1]+f[n2]n3

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

f[1]f[2]
11

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

f[1]f[2]f[3]
112

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

f[1]f[2]f[3]f[4]
1123

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

f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[n]
11235813

时间复杂度:O(n)

cpp
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[n1]+f[n2]

边界条件

一开始就知道的状态。

案例 的边界条件为

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

DP 步骤

  1. 为问题设计 状态
  2. 列出 状态转移方程
  3. 边界条件 开始,以 正确的顺序 求解所有状态。
递推和 DP 的区别

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

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

  • 当状态的计算顺序容易确定时,通常采用递推(如 案例 中采用线性顺序);
  • 当状态的计算顺序难以确定时,通常采用 记忆化搜索