动态规划状态表内存复用的核心是只存够用状态：滚动数组用一维替代二维，原地覆盖直接修改输入，状态精简用位运算压缩，空间复杂度可从O(m×n)降至O(n)甚至O(1)。

动态规划中状态表的内存复用，核心是让有限的数组空间承载不断演进的状态信息，而不是为每一层都开辟新内存。关键不在于“多存”，而在于“只存够用的”。

滚动数组：用一维替代二维

当状态转移只依赖上一行（或上一层）时，二维表就存在大量闲置空间。比如路径类问题中 f[i][j] = f[i-1][j] + f[i][j-1]，计算第 i 行时，第 i-2 行及更早的数据已无用。

• 直接把第一维压缩为 2，用 f[i%2][j] 和 f[(i-1)%2][j] 分别表示当前行与上一行
• 或进一步简化为单维数组，从右往左更新（如 0-1 背包）：dp[j] = max(dp[j], dp[j-w[i]] + v[i])，避免覆盖尚未使用的旧值
• 这种做法能把空间复杂度从 O(m×n) 降到 O(n)，甚至 O(1)（如斐波那契仅需两个变量）

原地覆盖：边算边丢旧状态

有些 DP 过程天然支持覆盖——当前状态只读取左侧或上方的值，且自身不会被后续同层计算反复引用。这时无需额外数组，直接在输入数据上修改即可。

• 例如最小路径和问题：grid[i][j] += min(grid[i-1][j], grid[i][j-1])，只要按行主序遍历，每格更新后旧值就不再需要
• 注意边界处理：首行首列需单独初始化，避免越界或误用未更新值
• 优点是零额外空间；缺点是会破坏原始输入，若需保留原数组则不可用

状态精简：用位或布尔压缩表达

当状态本身维度高但取值范围极小（如只有 true/false、0/1/2），可用位运算或紧凑类型替代整型数组。

• 状压 DP 中常用 int 或 uint64 的每一位表示一个元素是否被选中，mask & (1 判断第 i 位
• 布尔型 DP 可用 []bool 替代 []int，空间减半；极端情况还可打包成 bitset，8 倍压缩
• 适用前提是状态转移逻辑能适配位操作，且总状态数不超过机器字长限制（如 64 位最多处理 64 个二元状态）

变量不是越多越好，而是刚好够推下去。空间优化不是抠字节，是看清哪些状态真正在参与计算，其余的，该扔就扔。