1.题目

  • F(0) = 0, F(1) = 1
  • F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

    2.解法

2.1 普通递归

1
2
3
4
5
6
private int fib(int n){
     if(n<2)
         return n;
     else
         return fib(n-1)+fib(n-2);
}

2.2 字典记录

将每一次计算的值记录下来

1
2
3
4
5
6
7
8
9
10
private int fibs(int n){
    int[] Results=new int[n+1];
    for(int i=0;i<n+1;i++){
        if(i<2)
            Results[i]=i;
        else
            Results[i]=Results[i-1]+Results[i-2];
    }
    return Results[n];
}

2.3 动态规划

每一项的值为前两项的值之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int fib(int n) {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        int prePre = 0, pre = 1, curr = 0;
        for(int i = 2; i <= n; i++){
            curr = (prePre + pre);
            prePre = pre;
            pre = curr;
        }
        return curr;
    }
}