斐波那契数,通常用 F(n)
表示,形成的序列称为 斐波那契数列 。该数列由 0
和 1
开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1
示例 1:
输入:2 输出:1 解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2
输入:3 输出:2 解释:F(3) = F(2) + F(1) = 1 + 1 = 2
暴力递归法
class Solution { public int fib(int n) { if(n==0 || n==1) { return n; } return fib(n-1) + fib(n-2); } }
使用备忘录递归(有重复计算,记住原来的计算结果 就不用重复计算了)
class Solution { public int fib(int n) { //备忘录全初始化为 0 int [] memo = new int[n+1]; return helper(memo,n); } private int helper(int [] memo, int n) { //base case if(n==0 || n==1) return n; //已经计算过了,不用再计算了 if(memo[n] != 0) return memo[n]; memo[n] = helper(memo,n-1) + helper(memo,n-2) ; return memo[n]; } }
递归法自顶而下。我们现在来自底向上。
class Solution { public int fib(int n) { if(n==0) return 0; int [] dp = new int[n+1]; //base case dp[0] = 0; dp[1] = 1; //状态转移 for(int i =2;i <=n;i++) { dp[i] = dp[i-1]+dp[i-2]; } return dp[n]; } }
再次优化,优化dp空间,步需要那么多存储空间,只要两个就可以了。
class Solution { public int fib(int n) { //base case if(n==0 || n == 1 ) return n; //自底向上计算 //只用两个变量 记忆前两步值 int prev = 0,curr =1; for(int i =2;i <=n;i++) { int sum = prev+ curr; prev = curr; curr = sum; } return curr; } }