509. 斐波那契数

动态规划

class Solution {
    public int fib(int n) {

        /**
         * 动态规划
         */
         if (n < 2){
             return 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)
 */

优化1——滚动数组减小空间复杂度

class Solution {
    public int fib(int n) {

        /**
         * 动态规划
         * fib(n)只与fib(n - 1)和fib(n - 2)有关，因此不需要存储所有的值，只用两个变量存储这两个值
         * n从0开始
         */
        if (n < 2){
            return n;
        }

        int[] dp = new int[3];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 0;

        for (int i = 2; i <= n; i++) {

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

        return dp[1];
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

https://leetcode-cn.com/problems/fibonacci-number/