509. 斐波那契数(java动态规划实现)

class Solution {
    public int fib(int n) {
        /**
        这里我们把它作为动态规划 入门必做题第一题
            动态规划模板 图片里面有
            1 开一个[n+1]的备忘录,并附初始值  再开一个ans数组
            2穷举状态
            3转台转移(==  !=)
            4return xx[n]
         */
        int [] memo=new int[n+1];//备忘录模式(可有 可无)
        Arrays.fill(memo,-1);//并附初始值
        int []ans=new int[n+1];//开一个[n+1]的数组,
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        ans[0]=0;//并附初始值
        ans[1]=1;
        for(int i=2;i<=n;i++){//穷举状态
            if(memo[i]!=-1){
                ans[i]=memo[i];
            }else{
                 ans[i]=ans[i-1]+ans[i-2];//状态转移了
                 memo[i]=ans[i];
            }
        }
        return ans[n];
    }
}