动态规划

class Solution {
    public int fib(int n) {

        /**
         * 动态规划
         */
         if (n < 2){
             return n;
         }
         
        int[] value = new int[n + 1];

        value[0] = 0;
        value[1] = 1;

        for (int i = 2; i <= n; i++) {
            value[i] = value[i - 1] + value[i - 2];
        }

        return value[n];
    }
}

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

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

class Solution {
    public int fib(int n) {

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

        int a = 0;
        int b = 0;
        int c = 1;

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

            a = b;
            b = c;
            c = a + b;
        }

        return c;
    }
}

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

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