题解 | #斐波那契数列#
斐波那契数列
http://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3
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
}
*/