牛客题霸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);  //当前节点值等于前两项的和
     }
}

 

上一篇:面试中如何答好斐波那契数列fabnacci实现之java版?


下一篇:操作系统概念4.11linux下线程的创建