509. Fibonacci Number

Question

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Solution 1

记忆化搜索，在递归时递归过的n放入数组memo中记录。

Code

class Solution {
    int[] memo;
    public int fib(int n) {
        if(n == 0 || n == 1) return n;
        memo = new int[n+1];
        return fibo(n);
    }
    
    private int fibo(int n){
        if(n == 0 || n == 1) return n;
        if(memo[n] == 0) memo[n] = fibo(n-1) + fibo(n-2);
        return memo[n];
    }
}

Solution 2

递归，当n等于0或者1时返回固定值。
否则返回fib(n-1)+fib(n-2)。

Code

class Solution {
    public int fib(int n) {
        if(n == 0 || n == 1) return n;
        return fib(n-1) + fib(n-2);
    }
}