剑指 Offer 10- I. 斐波那契数列

  1. //滚动数组法,时间On，空间O1
  2. func fib(n int) int {
  3.     if n <= 1 {
  4.         return n
  5.     }
  7.     prev , cur := 0, 1
  9.     for i := 2; i <= n; i++ {
  10.         temp := (prev + cur) %1000000007
  11.         prev = cur
  12.         cur = temp
  13.     }
  15.     return cur             //返回cur 而不是temp，不需要初始化temp
  16. }
//时空都是On的解法
func fib(n int) int {
    if n <= 1 {
        return n
    }

    dp := make([]int, n +1)
    dp[0] , dp[1] = 0, 1

    for i := 2; i <= n; i++ {
        dp[i] = (dp[i-1] + dp[i-2]) %1000000007
    } 
    return dp[n]
}