《状压DP(01矩阵约束问题)》基础概念

一、算法概述

1. 问题定义：01矩阵约束问题是指在一个n×m的矩阵中放置0或1，满足特定约束条件（如相邻位置不能同时为1），并求最优解（如方案数、最大值、最小值等）。
2. 核心思想：状态压缩动态规划（状压DP）通过二进制数表示矩阵每行的状态，利用动态规划记录状态转移，高效解决此类问题。
3. 应用场景：
   • 棋盘放置问题（如N皇后变种）
   • 资源分配（相邻资源不能同时使用）
   • 电路布局（避免相邻电路干扰）

二、算法思路

1. 状态定义：
   • dp[cur][state]：处理到当前行cur时，该行状态为state的最优解。
   • state：二进制数，表示该行每个位置是0还是1。
2. 状态转移：
   • 枚举上一行状态prestate和当前行状态curstate。
   • 检查状态是否满足约束条件（如相邻位置不能同时为1）。
   • 更新状态转移方程。
3. 约束条件处理：
   • MatrixPutDP_canPut函数检查当前位置能否放置1。
   • 考虑上一行和左列的约束（根据MaskType决定）。
4. 滚动数组优化：
   • 使用两个一维数组dp[2][]交替存储当前行和上一行的状态，降低空间复杂度。

三、伪代码实现

1. 数据结构与全局变量

常量 maxn = 20  # 矩阵最大行数
常量 maxm = 20  # 矩阵最大列数
常量 MaskType = (Mask.UP | Mask.LEFT)  # 约束类型：上方和左方
常量 mod = 100000000  # 取模常量
变量 dptype = DPType.NUM  # 问题类型：方案数二维数组 dp[2][1<<maxm]  # 滚动数组存储状态
二维数组 grid[maxn][maxm]  # 矩阵，记录每个位置的类型枚举 DPType:MIN = 0  # 最小值MAX = 1  # 最大值NUM = 2  # 方案数MOD = 3  # 方案数取模枚举 GridType:EMPTY = -1  # 可放置ZERO = 0    # 必须放0ONE = 1     # 必须放1枚举 Mask:UP = (1<<0)    # 上方约束LEFT = (1<<1)  # 左方约束

2. 核心函数

函数 MatrixPutDP_Opt(cur, pre, curOneCount):# 根据问题类型选择最优操作if dptype == DPType.MIN:return min(cur, pre + curOneCount)else if dptype == DPType.MAX:return max(cur, pre + curOneCount)else if dptype == DPType.NUM:return cur + preelse:  # MODreturn (cur + pre) % mod函数 MatrixPutDP_ValueInf():# 返回无穷值（根据问题类型）if dptype == DPType.MIN:return 1000000000else if dptype == DPType.MAX:return -1000000000else:  # NUM or MODreturn 0函数 MatrixPutDP_ValueInit():# 返回初始值（根据问题类型）if dptype == DPType.MIN:return 0else if dptype == DPType.MAX:return 0else:  # NUM or MODreturn 1函数 MatrixPutDP_canPut(prestate, curstate, r, c):# 检查位置(r,c)能否放置1if grid[r][c] != GridType.EMPTY:return falseif MaskType & Mask.UP:if r > 0 and grid[r-1][c] == GridType.ONE:return falseif prestate & 1:  # 上一行对应位置为1return falseif MaskType & Mask.LEFT:if c > 0 and grid[r][c-1] == GridType.ONE:return falseif (curstate>>1) & 1:  # 当前行左列位置为1return falsereturn true函数 MatrixPutDP_DFS(col, maxcol, row, pre, prestate, cur, curstate, cnt):# 深度优先搜索生成合法状态if col == maxcol:dp[cur][curstate] = MatrixPutDP_Opt(dp[cur][curstate], dp[pre][prestate], cnt)returnfor i from 0 to 1:  # 枚举上一行当前列的值pres = prestate<<1 | ifor j from 0 to 1:  # 枚举当前行当前列的值curs = curstate<<1 | jif j == GridType.ONE:  # 当前位置放1if not MatrixPutDP_canPut(pres, curs, row, col):continueMatrixPutDP_DFS(col+1, maxcol, row, pre, pres, cur, curs, cnt + j)函数 MatrixPutDP_Solve(n, m):# 解决01矩阵约束问题# 1. 初始化pre = 0, cur = 1for i from 1 to (1<<m)-1:dp[pre][i] = MatrixPutDP_ValueInf()dp[pre][0] = MatrixPutDP_ValueInit()# 2. 状态转移for i from 0 to n-1:for j from 0 to (1<<m)-1:dp[cur][j] = MatrixPutDP_ValueInf()MatrixPutDP_DFS(0, m, i, pre, 0, cur, 0, 0)swap(pre, cur)  # 滚动数组# 3. 结果结算ans = MatrixPutDP_ValueInf()for j from 0 to (1<<m)-1:ans = MatrixPutDP_Opt(ans, dp[pre][j], 0)return ans# 主程序
输入 n, m
初始化 grid 所有元素为 GridType.EMPTY
输出 MatrixPutDP_Solve(n, m)

四、算法解释

1. 状态压缩

• 用二进制数state表示矩阵每行的状态，如state = 101表示该行第0和第2列放1，第1列放0。
• 滚动数组dp[2][]交替存储当前行和上一行的状态，节省空间。

2. 约束条件检查

• MatrixPutDP_canPut函数检查：
  • 当前位置是否允许放置。
  • 上方和左方约束是否满足（根据MaskType）。
• 递归生成合法状态，避免无效计算。

3. 深度优先搜索

• MatrixPutDP_DFS枚举每列的可能值（0或1），生成合法状态。
• cnt参数记录当前行放置的1的数量，用于某些问题类型（如最大值、最小值）。

4. 状态转移

• 遍历所有可能的上一行和当前行状态，更新dp数组。
• 根据问题类型（MIN/MAX/NUM/MOD）选择不同的状态转移方式。

5. 结果计算

• 遍历最后一行的所有状态，根据问题类型选择最优解（如方案数、最大值等）。

五、复杂度分析

1. 时间复杂度：
   • 状态数：$O(n\times 2^m)$（$n$行，每行$2^m$种状态）。
   • 每个状态转移：$O(4^m)$（枚举上一行和当前行的所有可能组合）。
   • 总时间复杂度：$O(n\times 4^m)$。
2. 空间复杂度：
   • DP数组：$O(2\times 2^m)=O(2^m)$（滚动数组优化）。
   • 矩阵：$O(n\times m)$。
   • 总空间复杂度：$O(n\times m+2^m)$。
3. 优化点：
   • 预处理合法状态，减少递归次数。
   • 进一步状态压缩（若约束允许）。
4. 适用范围：
   • 适用于$m$较小的情况（通常$m\le 20$），因为$4^m$的复杂度随$m$增大而迅速增长。

---

  本文为作者（英雄哪里出来）在抖音的独家课程《英雄C++入门到精通》、《英雄C语言入门到精通》、《英雄Python入门到精通》三个课程的配套文字讲解，如需了解算法视频课程，请移步 作者本人 的抖音直播间。