牛客题霸NC65斐波那契数列Java题解
方法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); //当前节点值等于前两项的和 } }