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

斐波那契数列是指从第三项开始，每一项都是前两项的和，即：F(n) = F(n-1) + F(n-2)。

为了使用动态规划求解斐波那契数列的第 n 项，我们需要定义一个数组 dp，其中 dp[i] 表示第 i 个斐波那契数。

根据斐波那契数列的定义，我们可以得到如下动态规划的转移方程：

dp[i] = dp[i-1] + dp[i-2]

初始值：

dp[0] = 0 dp[1] = 1

根据转移方程，我们可以依次计算出 dp[2]、dp[3]、dp[4]、...、dp[n] 的值，最终得到斐波那契数列的第 n 项。

例如，当 n = 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。