C#动态规划的状态压缩技巧（从零开始掌握空间优化的实战方法）

案例1：斐波那契数列（基础状态压缩）

斐波那契数列是最简单的动态规划问题之一。常规写法如下：

// 普通 DP 写法（空间复杂度 O(n)）public int Fib(int n){    if (n <= 1) return n;    int[] dp = new int[n + 1];    dp[0] = 0;    dp[1] = 1;    for (int i = 2; i <= n; i++)    {        dp[i] = dp[i - 1] + dp[i - 2];    }    return dp[n];}  

使用状态压缩技巧后，我们只需两个变量：

// 状态压缩写法（空间复杂度 O(1)）public int FibOptimized(int n){    if (n <= 1) return n;    int prev2 = 0; // dp[i-2]    int prev1 = 1; // dp[i-1]    int current = 0;    for (int i = 2; i <= n; i++)    {        current = prev1 + prev2;        prev2 = prev1;        prev1 = current;    }    return current;}  

案例2：0-1 背包问题（二维转一维）

0-1 背包是动态规划中的经典问题。原始 DP 方程为：

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

观察发现：dp[i][...] 只依赖于 dp[i-1][...]。因此我们可以将二维数组压缩为一维数组。

// 0-1 背包：状态压缩版本public int Knapsack(int capacity, int[] weights, int[] values){    int n = weights.Length;    int[] dp = new int[capacity + 1];    for (int i = 0; i < n; i++)    {        // 注意：必须从后往前遍历，避免重复使用同一物品        for (int w = capacity; w >= weights[i]; w--)        {            dp[w] = Math.Max(dp[w], dp[w - weights[i]] + values[i]);        }    }    return dp[capacity];}  

这里关键点在于内层循环要 从大到小 遍历容量 w。如果从小到大遍历，会导致同一个物品被多次使用（变成完全背包问题）。

什么时候可以使用状态压缩？

• 当前状态仅依赖于前一个或前几个状态；
• 状态转移方程中不涉及“跳跃式”依赖（如 dp[i] 依赖 dp[i-3] 和 dp[i-5]，但中间状态无用）；
• 问题不要求输出完整的路径或中间过程，只需最终结果。

总结

通过本文的学习，你应该已经掌握了 C#动态规划 中的 状态压缩技巧。这种 动态规划空间优化 方法不仅能节省大量内存，在处理大规模数据时还能显著提升程序效率。

记住：状态压缩不是万能的，但它在合适场景下非常强大。多练习、多思考，你也能写出高效又优雅的 C# 算法代码！

关键词回顾：C#动态规划、状态压缩技巧、C#算法优化、动态规划空间优化