Appearance
案例
我们从一个案例入手 DP。
斐波那契数列又称黄金分割数列,其数值为
其中每一项都等于前两项之和。计算该数列的第
根据数列的特征,容易列出递推公式:
首先,将
计算
计算
重复计算填表的步骤,直到得到
时间复杂度:
cpp
f[1] = f[2] = 1;
for (int i = 3; i <= n; i ++)
f[i] = f[i - 1] + f[i - 2];
术语
状态
状态是表格中所填数字的意义。
案例 的状态
状态转移方程
描述状态间关系的方程。
案例 的状态转移方程为
边界条件
一开始就知道的状态。
案例 的边界条件为