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

斐波那契数列是一个递归定义的数列，即 F(n) = F(n-1) + F(n-2)，其中 F(0) = 0，F(1) = 1。

动态规划法是一种将原问题拆分成若干个子问题并且保存子问题的解的方法。在求解斐波那契数列的第 n 项时，可以利用动态规划的思想，保存前面的子问题的解，从而避免重复计算。

具体而言，可以使用一个数组 dp 来保存斐波那契数列的前 n 项，其中 dp[i] 表示第 i 项的值。初始时，dp[0] = 0，dp[1] = 1。然后，从 i=2 开始，依次计算 dp[i] = dp[i-1] + dp[i-2]，直到计算出 dp[n] 为止。

例如，当 n = 6 时，dp 数组的计算过程如下所示：

dp[0] = 0 dp[1] = 1 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 dp[6] = dp[5] + dp[4] = 5 + 3 = 8

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