剑指offer第七题。

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

解题思路

最简单的解法就是递归了：

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }else if(n == 1 || n == 2){
            return 1;
        }else{
            return Fibonacci(n-1) + Fibonacci(n-2);
        }
    }
}

但是递归存在重复子问题，所以时间复杂度较高，但是这里竟然通过了？斐波那契数列我认为最优的一个解法是用两个变量存储。

这题目用动态规划来解其实是不好的，至少逆向思考问题本身就是比较问难的，我觉得这种记忆化搜索对于这种问题是最好理解并且解是比较优的解。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        int a = 1;
        int b = 1;
        int c = 0;
        for(int i=2;i<n;i++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}