Go语言中的动态规划实战（从斐波那契数列入门动态规划）

为什么用动态规划？

很多人一开始会用递归来写斐波那契，但这样效率极低（时间复杂度 O(2ⁿ)），因为存在大量重复计算。而动态规划的核心思想是：记住已经算过的子问题结果，避免重复计算。

方法一：递归（不推荐）

func fibRecursive(n int) int {    if n <= 1 {        return n    }    return fibRecursive(n-1) + fibRecursive(n-2)}

虽然代码简洁，但当 n 较大时（比如 n=50），程序会卡死很久！

方法二：动态规划（自底向上）

我们用一个数组 dp 来保存中间结果，dp[i] 表示第 i 项的斐波那契值。

func fibDP(n int) int {    if n <= 1 {        return n    }    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]}

时间复杂度降为 O(n)，空间复杂度 O(n)。

方法三：空间优化版动态规划

其实我们只需要前两项的值，不需要整个数组。因此可以只用两个变量来记录，进一步节省内存。

func fibOptimized(n int) int {    if n <= 1 {        return n    }    prev2 := 0 // F(0)    prev1 := 1 // F(1)    curr := 0    for i := 2; i <= n; i++ {        curr = prev1 + prev2        prev2 = prev1        prev1 = curr    }    return curr}

现在时间复杂度仍是 O(n)，但空间复杂度降到 O(1)！这是最优解。

完整可运行示例

package mainimport "fmt"func fibOptimized(n int) int {    if n <= 1 {        return n    }    prev2, prev1 := 0, 1    for i := 2; i <= n; i++ {        prev2, prev1 = prev1, prev1+prev2    }    return prev1}func main() {    fmt.Println("F(10) =", fibOptimized(10)) // 输出: F(10) = 55}

总结

通过这个简单的Go算法教程，你已经掌握了动态规划入门的核心思想：用空间换时间，避免重复计算。斐波那契只是起点，后续你还可以用类似思路解决爬楼梯、打家劫舍、背包问题等经典题目。

记住：动态规划 = 状态定义 + 状态转移方程 + 初始条件 + 返回值。

希望这篇关于Go语言动态规划和斐波那契数列的教程对你有帮助！快动手写一写代码，加深理解吧！