package DP;
//斐波那契 备忘录法
public class test1 {
    public static void main(String[] args) {
        Solution01 solution01 = new Solution01();
        int a=solution01.Fibonacci(4);
        System.out.println(a);

    }

}
class Solution01 {
    public int Fibonacci(int n) {
        int Memo[]=new int[n+1];
        for (int i = 0; i < Memo.length; i++) {
            Memo[i]=-1;
        }
        return fib(n,Memo);
    }
    public int fib(int n,int Memo[]){
        int res=0;
        Memo[0]=0;
        if (n==1){
            Memo[n]=1;
            res=Memo[n];
        }
        if (n>=2){
            if (Memo[n]!=-1){
                res=Memo[n];
            }
            else{
                Memo[n]=fib(n-1,Memo)+fib(n-2,Memo);
                res=Memo[n];
            }
        }

        return res;
    }
}

自底向上

public class Solution {
    public int Fibonacci(int n) {
        int Memo[]=new int[n+1];
        Memo[0]=0;
        Memo[1]=1;
        for (int i = 2; i <=n; i++) {
            Memo[i]=Memo[i-2]+Memo[i-1];
        }
        if (n<=0){
            return n;
        }
        return Memo[n];

    }
}