- 暴力递归
func fib(n int) int { | |
if n == 0 || n== 1{ | |
return 1 | |
} | |
return fib(n-1) + fib(n-2) | |
} |
- 带备忘录的递归
func fib(n int) int { | |
memo := make([]int,n+1) | |
return dp(memo,n) | |
} | |
func dp(memo []int,n int) int { | |
if n == 0 || n == 1{ | |
return | |
} | |
if memo[n] != 0{ | |
return memo[n] | |
} | |
memo[n] = dp(memo,n-1) + dp(memo,n-2) | |
return memo[n] | |
} |
- 动态规划
func fib(n int) int { | |
if n == 0 { | |
return 0 | |
} | |
dp := make([]int,n+1) | |
dp[0] = 0 | |
dp[1] = 1 | |
for i := 2;i <= n;i++{ | |
dp[i] = dp[i-1] + dp[i-2] | |
} | |
return dp[n] | |
} |
- 动态规划优化
func fib(n int) int { | |
if n == 0 { | |
return 0 | |
} | |
dp_i_1 := 0 | |
dp_i_2 := 1 | |
for i := 2;i <= n;i++{ | |
dp_i = dp_i_1 + dp_i_2 | |
dp_i_1 = dp_i_2 | |
dp_i_2 = dp_i | |
} | |
return dp_i | |
} |
