如何使用动态规划计算N×M棋盘上放置任意数量互不攻击骑士的方案数

核心规则梳理 #

骑士的攻击位移为行差±1、列差±2，或行差±2、列差±1，因此两个骑士只要不存在上述位移关系即合法。我们通常取M ≤ N（若维度反过来可交换M和N，位掩码取短边长度降低计算量），用长度为M的整数作为位掩码，第k位为1表示该行第k列放置骑士，为0表示空位。

冲突校验规则 #

所有合法的状态组合只需要满足以下两类校验即可，无需额外校验单行状态（同一行骑士行差为0，不可能互相攻击）：

1. 相邻行（行差为1）无冲突：设当前行掩码为cur，上一行掩码为prev1，需满足：

   (cur & (prev1 << 2)) == 0 && (cur & (prev1 >> 2)) == 0
   

   该规则排除了行差1、列差±2的攻击情况。
2. 隔行（行差为2）无冲突：设当前行掩码为cur，上上行掩码为prev2，需满足：

   (cur & (prev2 << 1)) == 0 && (cur & (prev2 >> 1)) == 0
   

   该规则排除了行差2、列差±1的攻击情况。

动态规划设计 #

状态定义 #

由于判断当前行合法性仅需要前两行的放置状态，我们定义：
dp[i][a][b] = 处理完前i行，第i行状态为a、第i-1行状态为b时的总合法方案数。
如果需要优化空间，可以仅保留前两行的状态映射，无需存储所有行的DP结果。

基准条件（边界初始化） #

1. 第1行（i=1）：不存在前置行，所有可能的掩码a都合法，因此dp[1][a][0] = 1，其中0代表第0行全空的虚拟状态。
2. 第2行（i=2）：遍历所有第1行的合法状态a，再遍历所有可能的掩码b，若b和a满足相邻行无冲突规则，则dp[2][b][a] += dp[1][a][0]。

转移规则 #

对于第i行（i≥3）：

• 遍历所有存在计数的前序状态dp[i-1][prev1][prev2]（若计数为0可直接跳过减少计算量）
• 遍历所有可能的当前行掩码cur
• 若cur与prev1满足相邻行无冲突、cur与prev2满足隔行无冲突，则更新：

  dp[i][cur][prev1] += dp[i-1][prev1][prev2]
  

结果统计 #

遍历所有合法的a、b组合，将所有dp[N][a][b]的计数求和，即为N×M棋盘的总合法放置方案数。

可选优化 #

1. 预过滤掩码对：提前计算所有合法的相邻掩码对、隔行掩码对，转移时直接遍历合法组合，无需每次做位运算校验，能大幅提升计算效率。
2. 矩阵快速幂优化：若N的取值极大（如1e9级别），可以将状态转移转化为矩阵乘法，用快速幂计算N次转移后的结果，时间复杂度可降低到O(S³logN)，其中S是合法状态对的数量。
3. 二分图拆分优化：利用骑士仅攻击同色棋盘格的性质，可将棋盘拆分为黑白两个独立的二分图，总方案数等于两个二分图的独立集计数的乘积，对于部分场景可以进一步降低计算量。

内容的提问来源于stack exchange，提问作者anon comp