509. 斐波那契数（Java、动态规划）

动态规划入门基础 重叠子问题
三种方法不断优化

class Solution {
    //1、暴力
    public int fib(int n) {
        if(n == 0||n==1){
            return n;
        }
        return fib(n-1)+fib(n-2);
    }
    //2、备忘录
    public int fib(int n) {
        
        int[] memo = new int[n+1];
        return helper(memo,n);
    }
    public int helper(int[] memo,int n){
        if(n==0||n==1){
            return n;
        }
        if(memo[n]!=0){
            return memo[n];
        }
        memo[n] = helper(memo,n-1)+helper(memo,n-2);
        return memo[n];
    }
    //3、dpTable
    public int fib(int n) {
        if(n==0||n==1){
            return n;
        }
        int dp1 = 0;int dp2 = 1;
        for(int i = 2;i<=n;i++){
            int dp = dp1+dp2;
            dp1 = dp2;
            dp2 = dp;
        }
        return dp2;
    }
 
}