java 剑指offer之[数据结构 中等]JZ7 斐波那契数列

题目的链接在这里：https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3

题目大意

一、示意图

二、解题思路

递归和动态规划

递归

代码如下：

public class Solution {public int Fibonacci(int n) {//一般是直接用递归的if(n==0)return 0;if(n==1||n==2)return 1;return Fibonacci(n-1)+Fibonacci(n-2);}
}

动态规划

代码如下：

public class Solution {public int Fibonacci(int n) {//动态规划if(n<=1)return n;int[] dp=new int[n+1];dp[0]=0;dp[1]=1;for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
}