剑指Offer:斐波那契数列(10.1)

题目描述:

求斐波那契数列的第 n 项，n <= 39。

解题思路:

如果使用递归求解，会重复计算一些子问题。例如，计算 f(4) 需要计算 f(3) 和 f(2)，计算 f(3) 需要计算 f(2) 和 f(1)，可以看到 f(2) 被重复计算了。

1 public class Solution {
2     public int Fibonacci(int n) {
3         if(n<=1){
4             return n;
5         }
6         return Fibonacci(n-1)+Fibonacci(n-2);
7     }
8 }

递归会重复计算大量相同数据，我们可以用个数组把结果存起来！

 1 public class Solution {
 2     public int Fibonacci(int n) {
 3         int ans[] = new int[40];
 4         ans[0] = 0;
 5         ans[1] = 1;
 6         for(int i=2;i<=n;i++){
 7             ans[i] = ans[i-1] + ans[i-2];
 8         }
 9         return ans[n];
10     }
11 }

后续还可以继续优化...