有序编号球分盒方案计数算法及两类扩展问题求解

基础问题解法 #

核心规则：球的排列顺序固定，分组为连续段，无空盒。

• 数学结论：总方案数为 2^(N-1)。原理是N个球之间共有N-1个相邻间隙，每个间隙可以选择插入隔板分组，也可以选择不插，所有选择的组合对应所有合法分组。
• 暴力搜索实现思路：
  采用回溯法实现：
  • 记录当前处理到的球的起始位置 pos
  • 遍历当前盒子可选择的球数 m，取值范围为1到剩余球总数 N-pos+1
  • 选定m个球放入当前盒子后，递归处理pos+m位置的剩余球
  • 当pos超过N时，统计为1种合法方案

扩展问题1：后一个盒子球数≥前一个盒子球数 #

采用动态规划解决：

• 状态定义：dp[i][j] 表示处理完前i个球，且最后一个盒子的球数为j时的合法方案总数
• 状态转移：dp[i][j] = 所有满足 t ≤ j 的 dp[i-j][t] 的和，其中要求i-j ≥ 0，保证前i-j个球合法存在
• 边界条件：对所有1≤j≤N，dp[j][j] = 1，对应前j个球全部放到第一个盒子的情况
• 最终结果：所有dp[N][j]的和，j取值范围为1到N
• 性能优化：可以前缀和预处理每个位置的求和结果，将时间复杂度从O(N^3)降到O(N2)

扩展问题2：后一个盒子球数≥前一个的k倍 #

逻辑和扩展问题1基本一致，仅修改状态转移的判定条件即可：

• 状态转移改为：dp[i][j] = 所有满足 t*k ≤ j 的 dp[i-j][t] 的和
• 边界条件、结果计算逻辑和扩展问题1完全相同

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