509. 斐波那契数

509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给你 n ，请计算 F(n) 。

//自顶向下，分治+记忆化
func fib(n int) int {
    if n <= 1 {
        return n
    }
    nums := make([]int, 31) 
    nums[0] = 0
    nums[1] = 1
    for i:= 2; i<= n; i++ {
        nums[i] = nums[i-1] +nums[i-2]        //这就是记忆化，空间On，但是节约了每层查找
    }
    return nums[n]
}

//动规,自底向上for 时间On，空间O1
func fib(n int) int {
    if n < 2 {
        return n        //结束条件，递归起点
    }

    a, b := 0, 1
    temp := 0            //初始条件

    for i:= 2; i<= n; i++ {            //最优子结构，dp核心，只考虑自己和手下
        temp = a + b
        a = b
        b = temp
    }
    return temp
}