牛客题霸NC65斐波那契数列Java题解

牛客题霸NC65斐波那契数列Java题解
https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=117&&tqId=34987&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
方法1：动态规划
解题思路：当n==0时，返回0，当0<n<=2时，返回1。
定义一个数组res用来存放斐波那契数列。斐波那契数列的的当前项只与它的前两项有关。
所以，利用for循环,求得斐波那契数列的每一项并保存在数组res中，最后返回res[n]，就是斐波那契数列的第n项。

public class Solution {
    public int Fibonacci(int n) {
        if(n==0){
            return 0;
        }

        if(n<=2){
            return 1;
        }

        int[] res = new int[n+1];   //用于保存斐波那契数列

        res[0] = 0;
        res[1] = 1;

        for(int i=2;i<=n;i++){
            res[i] = res[i-1]+res[i-2];  //当前节点值等于前两项的和
        }
        return res[n];
    }
}

方法2：递归
解题思路：当n==0时,返回0，当0<n<=2时，返回1，当n>2时，返回Fibonacci(n-1)+Fibonacci(n-2)。

public class Solution {
     public int Fibonacci(int n) {
         if(n==0){
             return 0;
         }
         if(n<=2){
             return 1;
         }
         return Fibonacci(n-1)+Fibonacci(n-2);  //当前节点值等于前两项的和
     }
}