题解 | #斐波那契数列#

package main

//动态规划,时间On
func Fibonacci( n int ) int {
    if n <= 1 {
        return n
    }
    
    dp := make([]int, n+1)
    dp[1], dp[2] = 1, 1
    
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

/*
//状态压缩，空间O1
func Fibonacci( n int ) int {
    if n <= 2 {
        return 1
    }
    
    temp := 0
    a, b := 1, 1
    
    for i := 2; i < n; i++ {
        temp = a + b 
        a = b 
        b = temp
    }
    return temp
}
*/