509. 斐波那契数

递归 动态规划

递归

直接递归很简单，直接返回n的n - 1 + n - 2就行，这也是递归的本质，你只需要写出递归出口和递归条件，剩下的都是程序帮你完成。

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

递归优化

上面直接递归虽然代码很简单，但是会产生多余的重复计算，比如下图fib(5)中会计算fib(4)，fib(6)也会计算fib(4)，所以递归的最好解决办法是使用备忘录的递归，把计算过的值存储下来，下次再去取这个值的时候先去表中找是否计算过了，会减少不必要的计算量。

class Solution {
  // 备忘录
    HashMap<Integer, Integer> map = new HashMap<>();
    public int fib(int n) {
      // 递归出口
        if(n < 2) return n;
      // 找到是否计算过了当前的fib值
        if(map.containsKey(n)) {
            return map.get(n);
        }
      // 没计算过当前fib就计算一下，然后存在备忘录中
        int a = fib(n - 1);
        int b = fib(n - 2);
        int tmp = a + b;
        map.put(n, tmp);
        return tmp;
    }
}

动态规划

在上面递归优化中使用了备忘录存储整个计算过程中的值，但我们站在fib(n)的角度上再审视一遍题目，我们算fib(n)时，需要的仅仅是fib(n - 1) + fib(n - 2)，算fib(n - 1)时需要fib(n - 2) + fib(n - 3)…

同理，我们从fib(2) fib(3)一直算到fib(n)，这条路上始终只用两个变量存储值，那么我们就不必像上面递归优化一样，把整个从1-n的所有fib值都存下来。这样，就可以实现整个逻辑。

class Solution {
    public int fib(int n) {
        if(n < 1) return 0;
        int a = 1;
        int b = 1;
        for(int i = 2; i < n; i ++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
}