Go语言动态规划的状态压缩（高效优化空间复杂度的实战技巧）

案例1：斐波那契数列（最简单的状态压缩）

斐波那契数列定义为：

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

普通DP写法需要一个长度为 n+1 的数组，但其实我们只需要前两个值。

// 普通DP（空间O(n)）func fibNormal(n int) int {    if n <= 1 {        return n    }    dp := make([]int, n+1)    dp[0], dp[1] = 0, 1    for i := 2; i <= n; i++ {        dp[i] = dp[i-1] + dp[i-2]    }    return dp[n]}// 状态压缩（空间O(1)）func fibCompressed(n int) int {    if n <= 1 {        return n    }    prev2, prev1 := 0, 1    for i := 2; i <= n; i++ {        curr := prev1 + prev2        prev2 = prev1        prev1 = curr    }    return prev1}

可以看到，通过只保留 prev1 和 prev2，我们将空间复杂度从 O(n) 降到了 O(1)。这就是最基础的 Go语言动态规划的状态压缩 应用。

案例2：0-1背包问题的状态压缩

0-1背包是DP中的经典问题。给定 n 个物品，每个物品有重量 w[i] 和价值 v[i]，背包容量为 W，求最大价值。

标准二维DP方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

注意：dp[i][j] 只依赖于上一行（i-1）的数据。因此，我们可以用一维数组来代替二维数组，但必须倒序遍历容量 j，避免覆盖还未使用的数据。

// 0-1背包：状态压缩版（空间O(W)）func knapsack(weights, values []int, W int) int {    n := len(weights)    // dp[j] 表示容量为j时的最大价值    dp := make([]int, W+1)    for i := 0; i < n; i++ {        // 倒序遍历！防止重复使用当前物品        for j := W; j >= weights[i]; j-- {            if dp[j] < dp[j-weights[i]] + values[i] {                dp[j] = dp[j-weights[i]] + values[i]            }        }    }    return dp[W]}

这里的关键点是：内层循环必须从大到小遍历。如果从小到大遍历，就会变成“完全背包”问题（允许重复选择），导致逻辑错误。

何时可以使用状态压缩？

判断是否能进行状态压缩，主要看以下两点：

1. 状态转移只依赖于有限的前几个状态（如前一行、前两个值等）；
2. 历史状态在后续计算中不再被使用。

如果你发现DP方程中 dp[i] 只与 dp[i-1]、dp[i-2] 有关，那么大概率可以压缩。

总结

通过本文，你已经掌握了 Go语言动态规划的状态压缩 的基本原理和实战技巧。无论是简单的斐波那契，还是复杂的背包问题，只要抓住“只保留必要状态”的核心思想，就能有效实现 空间复杂度优化。

记住：状态压缩不是改变算法逻辑，而是优化存储方式。它让我们的 Go算法优化 更加高效，尤其在内存受限的场景下至关重要。

多练习、多思考，你也能轻松驾驭 状态压缩DP！