题解 | #斐波那契数列#

动态规划解法：

public class Solution {
    public int Fibonacci(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]);
        }
        return dp[n];
    }
}

时间复杂度为 O(n)，空间复杂度为 O(n)，n 为要求解的斐波那契数列的项数。

感觉和跳台阶问题差不多：

跳台阶问题和斐波那契数列问题的递推公式是相同的，都是 f(n) = f(n-1) + f(n-2)，表示第 n 项等于前两项的和。

在跳台阶问题中，由于只能跳 1 级或 2 级台阶，因此初始值不同，即 f(1) = 1，f(2) = 2。

在斐波那契数列问题中，初始值为 f(0) = 0，f(1) = 1。