方法一

思路：递归

  1. func fib(n int) int {
  3.     if n <= 1 {
  4.         return n
  5.     }
  7.     return fib(n-1) + fib(n-2)
  8. }

方法二

思路：常数dp

func fib(n int) int {

    if n <= 1 {
        return n
    }

    prev, cur := 0, 1

    for i := 1; i < n; i++ {
        prev, cur = cur, prev + cur
    }
    return cur
}