题解 | 斐波那契数列

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    public int Fibonacci (int n) {

        int[] dp=new int[n+1];
        Arrays.fill(dp,-1);
        // write code here
        

        return dpsum(n,dp);
    }
    // 消除子问题  求一个问题 先求下面的

    public int dpsum (int n,int[] dp) {
        if(n==1 || n==2){
            return 1;
        }

        if(dp[n]!=-1){
            return dp[n];
        }
        dp[n]=dpsum(n-1,dp)+dpsum(n-2,dp);
        return dp[n];
    }
}