动态规划法求解斐波那契数列第 n 项

斐波那契数列是指：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2）。因此，求斐波那契数列的第 n 项，可以通过动态规划法求解。

具体步骤如下：

1. 定义状态：设 dp[i] 表示斐波那契数列的第 i 项的值。

2. 状态转移方程：根据斐波那契数列的定义，可以得到状态转移方程为 dp[i] = dp[i-1] + dp[i-2]。

3. 初始状态：根据斐波那契数列的定义，可以得到初始状态 dp[0] = 0，dp[1] = 1。

4. 边界条件：无。

5. 计算顺序：按照从小到大的顺序计算 dp[i]，最终得到 dp[n] 的值。

例如，要求斐波那契数列的第 5 项，可以按照上述步骤计算：

1. 定义状态：设 dp[i] 表示斐波那契数列的第 i 项的值。

2. 状态转移方程：dp[i] = dp[i-1] + dp[i-2]。

3. 初始状态：dp[0] = 0，dp[1] = 1。

4. 边界条件：无。

5. 计算顺序：按照从小到大的顺序计算 dp[i]，最终得到 dp[5] 的值。

按照状态转移方程，可以得到：

dp[2] = dp[1] + dp[0] = 1 + 0 = 1

dp[3] = dp[2] + dp[1] = 1 + 1 = 2

dp[4] = dp[3] + dp[2] = 2 + 1 = 3

dp[5] = dp[4] + dp[3] = 3 + 2 = 5

因此，斐波那契数列的第 5 项的值为 5。