package leecode;

/**
 * 斐波那契数列
 * 利用备忘录形式解决重叠子问题
 *
 * @author Tang
 * @date 2021/9/6
 */
public class Fibonacci {

    int[] nums;

    /**
     * 方法一:
     * 备忘录方法
     * @param n
     * @return
     */
    public int doIt(int n){

        nums = new int[n];
        return execute(n);
    }

    private int execute(int n) {
        if(nums[n - 1] != 0) {
            return nums[n - 1];
        }

        if(n == 1 || n == 2) {
            nums[n - 1] = 1;
            return nums[n - 1];
        }
        int value = execute(n - 1) + execute(n - 2);
        nums[n - 1] = value;
        return nums[n - 1];
    }

    /**
     * 方法二：
     * dp table构建
     * @param n
     * @return
     */
    public int doIt2(int n){
        int[] nums =  new int[n];

        //先计算出每一个元素的值
        for(int i = 0; i < n; i++) {
            if(i <= 1) {
                nums[i] = 1;
                continue;
            }
            nums[i] = nums[i - 1] + nums[i - 2];
        }
        return nums[n - 1];
    }

    public static void main(String[] args) {
        Fibonacci fibonacci = new Fibonacci();
        int execute = fibonacci.doIt2(10);
        System.out.println(execute);

    }




}

斐波那契数列