如何多项式时间计算带放置限制的n弹珠入n盒的合法方案数

问题梳理 #

我需要找到以下问题的更高效解法：
现有 n 个盒子 和 n 个种类完全不同的弹珠，每个盒子仅能放入指定种类的弹珠，且每个盒子恰好放1个弹珠。我之前看到过相关算法的描述但表述不够清晰，希望能得到准确的讲解。

示例说明

n=3
弹珠列表：2,5,3
各盒子的容纳限制（仅能放列表内的弹珠）：{5,2}、{3,5,2}、{3,2}
输出答案：3
合法方案对应的弹珠排列：{5,2,3}、{5,3,2}、{2,5,3}

我当前的解法时间复杂度为 O(2^n)，运行效率很低，已知额外限制如下：

• 存在所有盒子都能容纳的公共弹珠列表（上述示例中的公共弹珠为 2）
• 除公共弹珠外，每个盒子额外允许放入的弹珠最多只有 0、1 或 2 种
• 单个弹珠可放入的盒子编号差不超过 2

解法说明 #

结合给出的限制条件，可使用线性动态规划实现 O(n) 时间复杂度的计数，远优于现有 O(2^n) 方案，步骤如下：

1. 拆分弹珠类型降维
   将所有弹珠分为两类：
   • 公共弹珠：记集合大小为 k，所有盒子都可放置，放置时只需要考虑排列数
   • 非公共弹珠：记集合大小为 n-k，仅可在部分盒子放置
     我们可以先统计非公共弹珠的合法放置方案数，剩余空位直接放入公共弹珠，最终总方案数为 非公共放置方案数 × k!（k! 是公共弹珠的全排列数）。
2. 动态规划统计非公共弹珠放置方案
   根据限制「单个弹珠可放入的盒子编号差不超过2」，每个非公共弹珠的可选位置最多只有3个，且每个盒子最多允许2种非公共弹珠，因此只需要保存最近2个位置的占用状态即可完成转移，不需要记录全局所有位置的占用情况：
   定义 dp[i][s] 表示处理完前 i 个盒子时，最近2个盒子（i-1、i）的非公共弹珠占用状态为 s 的方案数。其中 s 为2位二进制数，0表示对应位置放公共弹珠，1表示放非公共弹珠，总共只有4种状态，状态空间极小。
   状态转移规则：

• 若第 i+1 个盒子放公共弹珠：将原状态右移1位，新的最后一位设为0，直接累加方案数
• 若第 i+1 个盒子放允许的非公共弹珠：检查该弹珠未被前2个位置占用，则转移状态，新的最后一位设为1，累加方案数

3. 结果合并
   将所有 dp[n][*] 的方案数求和得到非公共弹珠的总放置方案数，乘以公共弹珠的全排列数 k!，即可得到最终的总合法方案数。

示例验证

对应给出的示例，公共弹珠大小 k=1，非公共弹珠为 3、5，统计得到非公共弹珠的合法放置方案共3种，乘以 1! =1，最终结果为3，和示例输出一致。

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