带限制的整数划分问题（限制每个部分至少为某个值且最多使用k个部分） 题目描述 给定一个正整数 n ，以及两个额外的限制条件： 每个划分出来的正整数（即“部分”）必须 至少 为 minVal （一个给定的正整数）。 最多使用 k 个部分（即划分成的正整数个数不能超过 k ）。 请计算，将整数 n 划分成若干个正整数之和，并且满足上述两个限制条件的不同划分方案的数量。注意，划分是有顺序的，即 1+2 和 2+1 被视为两种不同的划分（这通常称为“有序划分”或“composition”）。 示例 ： 输入： n = 5, minVal = 1, k = 3 输出： 10 解释：满足条件的（有序）划分为： [1,1,3] , [1,2,2] , [1,3,1] , [2,1,2] , [2,2,1] , [3,1,1] , [1,4] , [4,1] , [2,3] , [3,2] （注意 [5] 也是1个部分，但它只用了1个部分，未超过 k=3 的限制，同时 5 >= minVal=1 ，因此也是有效的。所以总共有 10 种。实际上，我们列举了使用1个、2个、3个部分的所有可能。） 解题思路 这个问题可以被看作是一个线性动态规划问题，因为它涉及到在构建一个序列（划分序列）时，对总和的约束、对序列长度的约束以及对每个元素最小值的约束。我们可以从最基础的“有序划分”计数问题出发，逐步引入限制条件。 基础模型回顾 ： 不考虑 minVal 和 k 时，将整数 n 有序划分成正整数的方案数是经典的组合问题，答案是 2^(n-1) 。但我们这里需要用动态规划来求解，以便能融入限制。 核心定义 ： 我们定义 dp[i][j] 为：使用 恰好 j 个部分（正整数），并且这 j 个数的总和为 i 的 有序 划分方案数。 i 的范围是从 0 到 n （总和）。 j 的范围是从 0 到 k （部分数量）。 初始状态 ： dp[0][0] = 1 ：总和为0，使用0个部分，有一种方案（空划分）。这是动态规划的起点。 对于其他情况，当 i = 0 且 j > 0 时， dp[0][j] = 0 。因为没有正数相加能得到总和0（除了空划分）。 状态转移方程 ： 如何从较小的状态推导出 dp[i][j] ？ 考虑我们构建一个总和为 i 、有 j 个部分的划分。最后一个部分（第 j 个数字）可以是多少？ 由于每个部分必须至少为 minVal ，所以最后一个部分 last 的取值范围是： minVal <= last <= i （因为总和是 i ，并且前面已经有 j-1 个部分）。 如果我们固定最后一个部分是 last ，那么剩下的问题就是：总和为 i-last ，使用 j-1 个部分的方案数，即 dp[i-last][j-1] 。 因此，我们需要遍历所有可能的 last ，并求和： dp[i][j] = sum(dp[i-last][j-1]) ，其中 last 从 minVal 到 i 。 这个转移方程的含义是：要得到总和 i 的 j 个部分划分，我们可以从所有总和为 i - x 的 j-1 个部分划分方案后面，加上一个大小为 x （ x >= minVal ）的部分得到。 最终答案 ： 由于题目要求“最多使用 k 个部分”，所以最终答案不是 dp[n][k] ，而是所有使用 1 个部分到 k 个部分的方案数之和。即： ans = dp[n][1] + dp[n][2] + ... + dp[n][k] 。 详细步骤与示例演算 我们以 n=5, minVal=1, k=3 为例，手动计算一下动态规划表，验证输出是否为10。 初始化 ： 创建 dp 表，大小为 (n+1) x (k+1) ，即 6 x 4 。 dp[0][0] = 1 ，其余为0。 | i\j | 0 | 1 | 2 | 3 | |:----|:----|:----|:----|:----| | 0 | 1 | 0 | 0 | 0 | | 1 | 0 | | | | | 2 | 0 | | | | | 3 | 0 | | | | | 4 | 0 | | | | | 5 | 0 | | | | 按 i 从小到大， j 从小到大计算 ： 计算 i=1 : j=1 : dp[1][1] = sum(dp[1-last][0]) , last 从 minVal=1 到 1 。只有 last=1 。 dp[1-1][0] = dp[0][0] = 1 。所以 dp[1][1] = 1 。 j=2,3 : i=1 无法被分成2个或3个都 >=1 的数，所以为0。 | i\j | 0 | 1 | 2 | 3 | |:----|:----|:----|:----|:----| | 0 | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 0 | 0 | | 2 | 0 | | | | | 3 | 0 | | | | | 4 | 0 | | | | | 5 | 0 | | | | 计算 i=2 : j=1 : last 从1到2。 dp[2-1][0] + dp[2-2][0] = dp[1][0] + dp[0][0] = 0 + 1 = 1 。 所以 dp[2][1] = 1 （划分: [2] ）。 j=2 : last 从1到2。 dp[2-1][1] + dp[2-2][1] = dp[1][1] + dp[0][1] = 1 + 0 = 1 。 所以 dp[2][2] = 1 （划分: [1,1] ）。 j=3 : 不可能，为0。 | i\j | 0 | 1 | 2 | 3 | |:----|:----|:----|:----|:----| | 0 | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 0 | 0 | | 2 | 0 | 1 | 1 | 0 | | 3 | 0 | | | | | 4 | 0 | | | | | 5 | 0 | | | | 计算 i=3 : j=1 : last 从1到3。 dp[2][0] + dp[1][0] + dp[0][0] = 0+0+1 = 1 。( [3] ) j=2 : last 从1到3。 dp[2][1] + dp[1][1] + dp[0][1] = 1 + 1 + 0 = 2 。划分: ( last=1 时，前面是 [2] -> [2,1] ; last=2 时，前面是 [1] -> [1,2] 。 last=3 时， dp[0][1]=0 无效) j=3 : last 从1到3。 dp[2][2] + dp[1][2] + dp[0][2] = 1 + 0 + 0 = 1 。划分: ( last=1 时，前面是 [1,1] -> [1,1,1] ) | i\j | 0 | 1 | 2 | 3 | |:----|:----|:----|:----|:----| | 0 | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 0 | 0 | | 2 | 0 | 1 | 1 | 0 | | 3 | 0 | 1 | 2 | 1 | | 4 | 0 | | | | | 5 | 0 | | | | 计算 i=4 : j=1 : last 从1到4。 dp[3][0] + dp[2][0] + dp[1][0] + dp[0][0] = 0+0+0+1=1 ( [4] ) j=2 : last 从1到4。 dp[3][1] + dp[2][1] + dp[1][1] + dp[0][1] = 1+1+1+0=3 。( [3,1] , [2,2] , [1,3] ) j=3 : last 从1到4。 dp[3][2] + dp[2][2] + dp[1][2] + dp[0][2] = 2+1+0+0=3 。( [2,1,1] , [1,2,1] , [1,1,2] ) | i\j | 0 | 1 | 2 | 3 | |:----|:----|:----|:----|:----| | 0 | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 0 | 0 | | 2 | 0 | 1 | 1 | 0 | | 3 | 0 | 1 | 2 | 1 | | 4 | 0 | 1 | 3 | 3 | | 5 | 0 | | | | 计算 i=5 : j=1 : last 从1到5。 dp[4][0] + dp[3][0] + dp[2][0] + dp[1][0] + dp[0][0] = 0+0+0+0+1=1 ( [5] ) j=2 : last 从1到5。 dp[4][1] + dp[3][1] + dp[2][1] + dp[1][1] + dp[0][1] = 1+1+1+1+0=4 。( [4,1] , [3,2] , [2,3] , [1,4] ) j=3 : last 从1到5。 dp[4][2] + dp[3][2] + dp[2][2] + dp[1][2] + dp[0][2] = 3+2+1+0+0=6 。( [3,1,1] , [2,2,1] , [2,1,2] , [1,3,1] , [1,2,2] , [1,1,3] ) | i\j | 0 | 1 | 2 | 3 | |:----|:----|:----|:----|:----| | 0 | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 0 | 0 | | 2 | 0 | 1 | 1 | 0 | | 3 | 0 | 1 | 2 | 1 | | 4 | 0 | 1 | 3 | 3 | | 5 | 0 | 1 | 4 | 6 | 计算最终答案 ： 对于 n=5 ，我们累加 j=1 到 k=3 的部分： ans = dp[5][1] + dp[5][2] + dp[5][3] = 1 + 4 + 6 = 11 。 等等，我们之前说答案是10，怎么算出11？我们检查一下。 回忆一下我们的初始条件： dp[0][0] = 1 。这意味着“空划分”被视为一个方案。在我们 last 从 minVal 开始遍历时，对于 j=1 的情况，当 last = i 时，我们会用到 dp[0][0] 。这确实是对的，因为一个单独的部分 i 本身就是一个有效的划分。 在我们的例子中， dp[5][1] = 1 对应划分 [5] 。 dp[5][2] 和 dp[5][3] 的计算也依赖于更低 i 的 dp 值，而这些值又都依赖于 dp[0][0] 。 那么，我们的列举中是否漏掉了某个划分？让我们重新列举 n=5, minVal=1, k=3 的所有有效有序划分： 1部分: [5] 2部分: [1,4] , [2,3] , [3,2] , [4,1] (4种) 3部分: [1,1,3] , [1,2,2] , [1,3,1] , [2,1,2] , [2,2,1] , [3,1,1] (6种) 总数为 1 + 4 + 6 = 11 。而我们最初例子中给出的答案是10，并且列举了10种。我发现最初的列举 漏掉了 [5] ！所以正确答案应该是 11 。原始示例的描述有误（或者我最初理解有误）。根据我们动态规划的定义和计算，答案是11。 因此，动态规划的计算结果是正确的 。 算法总结 定义状态 ： dp[i][j] 表示总和为 i ，使用恰好 j 个部分（每个部分 >= minVal ）的有序划分方案数。 初始化 ： dp[0][0] = 1 ，其他为0。 状态转移 ：对于每个 i 从 1 到 n ，对于每个 j 从 1 到 k ，计算： dp[i][j] = Σ(dp[i - x][j - 1]) ，其中 x 从 minVal 到 i 。 计算结果 ：答案为 Σ(dp[n][j]) ，其中 j 从 1 到 k 。 复杂度与优化 时间复杂度 ：外层循环 i (O(n))，内层循环 j (O(k))，最内层求和需要遍历 x (O(n))，所以总复杂度为 O(n² * k)。对于较大的 n 和 k ，这可能会比较慢。 空间复杂度 ：O(n * k)。 可能的优化 ： 对于内层的求和 Σ(dp[i - x][j - 1]) ，这实际上是一个区间和（ x 从 minVal 到 i ）。我们可以使用 前缀和 技巧来优化。具体来说，在计算每一行 j 时，我们可以维护一个关于 i 的前缀和数组 prefixSum[i] = Σ(dp[i‘][j-1]) (i‘ 从0到i)。那么 Σ(dp[i - x][j - 1]) for x in [ minVal, i] 就等于 prefixSum[i-minVal] - prefixSum[i - (i+1)] ? 需要小心下标。 更准确地说，对于固定的 j ，我们要计算 dp[i][j] = sum_{x=minVal}^{i} dp[i-x][j-1] 。 设 t = i - x ，则当 x = minVal 时， t = i-minVal ；当 x = i 时， t = 0 。 所以求和变为 sum_{t=0}^{i-minVal} dp[t][j-1] 。这正是 dp[·][j-1] 从 0 到 i-minVal 的前缀和。 因此，我们可以预先计算出对于 j-1 这一列的前缀和数组 pre ，其中 pre[t] = sum_{u=0}^{t} dp[u][j-1] 。那么 dp[i][j] = pre[i - minVal] 。 通过前缀和优化，可以将最内层循环的复杂度从 O(n) 降到 O(1)，从而使总复杂度降至 O(n * k)。 变种与扩展 无序划分 ：如果划分是无序的（即 1+2 和 2+1 视为同一种），这就是经典的“整数划分”问题。通常需要不同的状态定义，例如 dp[i][j] 表示总和为 i ，最大部分不超过 j 的划分方案数。状态转移方程会有所不同。 每个部分有最大值限制 ：除了最小值 minVal ，可能还会限制每个部分不能超过 maxVal 。这时只需要在求和时修改 x 的上限为 min(i, maxVal) 即可。 完全背包视角 ：这个问题也可以被视为一个“完全背包”问题：背包容量为 n ，有 n 种物品（重量分别为 1,2,...,n ，但要求每种物品的重量至少为 minVal ），每种物品可以拿无限次，求 恰好装满背包 且 物品总个数不超过 k 的方案数。这里的“有序”对应着背包问题中考虑物品顺序的变体（通常称为“排列数”）。标准的完全背包求排列数的状态转移是 dp[i] += dp[i-weight] ，这里多了一个维度 j 来记录物品个数。