整数划分算法全解析：从递归到动态规划与实战应用

1. 项目概述从“分苹果”到算法核心整数划分这个名字听起来有点学术但它的内核其实非常生活化。想象一下你手头有5个一模一样的苹果要分给几个小朋友允许有小朋友分不到也允许把所有苹果都给一个人问一共有多少种不同的分法这就是整数划分问题最朴素的描述把一个正整数n拆分成若干个正整数的和不考虑顺序。比如5可以划分成5、41、32、311、221、2111、11111一共7种。这个问题在组合数学、数论、乃至物理如统计力学中的能级分配和计算机科学如资源分配、任务调度中都有广泛的应用。在算法设计与分析的课程或面试中整数划分是一个经典的动态规划和递归案例。它不像排序、查找那样有直接的库函数调用而是考验你如何将一个看似简单的计数问题抽象成状态转移方程并分析其时间空间复杂度。很多初学者第一次接触时会觉得“这不就是个暴力枚举吗”但一旦n稍微变大比如超过30枚举的复杂度就会指数级爆炸这时候高效的算法设计价值就凸显出来了。今天我们就来彻底拆解这个问题不仅告诉你“怎么做”更要讲清楚“为什么这么做”以及在实际编码和优化中会遇到哪些坑。2. 问题定义与数学建模2.1 精确的问题描述首先我们必须给“整数划分”一个严谨的定义因为不同的定义会导致完全不同的解空间和算法。我们讨论最常见的一种将正整数n表示成正整数之和的一种表示方法划分方式不同仅当和数不同与顺序无关。这里有几个关键点需要明确和数部分是正整数这意味着最小的划分单位是1。不考虑顺序32和23被视为同一种划分。这是划分Partition与组合Composition的核心区别组合是考虑顺序的。通常研究划分数p(n)即对于给定的n有多少种不同的划分方法。例如 p(5)7。为了后续算法设计我们通常会引入一个约束参数将原问题转化为一个更具操作性的子问题。最经典的两种定义方式是定义一划分中最大数不超过m。设q(n, m)表示将整数n划分为最大加数不超过m的划分个数。定义二划分成恰好k个部分。设p(n, k)表示将整数n划分为恰好k个部分的划分个数。这两种定义是等价的可以通过数学变换相互推导但它们引导出的递归关系和动态规划思路略有不同。在算法设计中第一种定义q(n, m)更为常用因为它能自然地导出一个二维的动态规划状态。2.2 从实例中寻找规律在动手写代码前先用小规模例子手动演算是理解问题、发现递推关系的最好方法。我们以q(n, m)为例手工计算一下小规模的划分数。我们可以构建一个表格行代表待划分的整数n列代表允许的最大部分mn\m12345111111212222312333413455513567这个表格怎么读q(5, 3)5表示将5划分为最大数不超过3的划分有5种分别是32, 311, 221, 2111, 11111。观察这个表格你能发现什么规律吗仔细看q(5,3)和它左上方的格子q(5,3) 5q(5,2) 3q(2,3) 2注意这里是q(5-3, 3)即q(2,3)似乎有q(5,3) q(5,2) q(2,3)。我们验证另一组q(4,3)4,q(4,2)3,q(1,3)1也满足4 3 1。这引导我们走向一个关键的分类讨论思路对于q(n, m)所有划分可以按照是否包含最大值m分为两类划分中不包含m那么所有部分都小于等于m-1其划分数就是q(n, m-1)。划分中包含至少一个m那么我们可以先拿出一个m来剩下的总和是n-m并且对这个n-m进行划分时最大部分仍然可以不超过m因为允许重复其划分数就是q(n-m, m)。由此我们得到了一个优美的递推关系递归式q(n, m) q(n, m-1) q(n-m, m)当然这个关系成立需要边界条件Base Case当n 0或m 1时无法划分q(n, m) 0。当n 0时无论m是多少我们认为有一种划分方式即什么都不划分一个空和q(0, m) 1。这是递归能够正确终止的关键。当n 1或m 1时只有一种划分全部是1q(n, 1) 1q(1, m) 1。注意这里的q(0, m)1是一个重要的技巧性定义。它对应着“恰好用一个最大数m划分完n”的情况。例如计算q(3,3)时包含3的划分情况是q(0,3)1对应着划分“3”本身。3. 核心算法设计与实现有了清晰的递推关系和边界条件我们就可以着手实现算法了。我们将从最直观但低效的递归开始逐步优化到动态规划并探讨其时间和空间复杂度。3.1 递归解法直观但低效的起点根据上面的递推式我们可以直接写出递归函数。这是理解问题逻辑最直接的方式。def partition_recursive(n, m): 返回将整数n划分为最大部分不超过m的划分数。 # 边界条件处理 if n 0 or m 1: return 0 if n 0: # 总和为0只有一种“空划分” return 1 if n 1 or m 1: # 只有全1一种划分 return 1 # 递推关系q(n,m) q(n, m-1) q(n-m, m) # 注意当 n-m 0 时递归调用会由第一个边界条件处理 return partition_recursive(n, m-1) partition_recursive(n-m, m) # 计算 p(5) q(5, 5) result partition_recursive(5, 5) print(f“整数5的划分数 p(5) {result}”) # 输出 7这段代码非常简洁正确性也容易理解。但是如果你尝试计算p(30)甚至p(50)程序可能会“卡住”很久。为什么呢因为递归调用树中存在大量的重复计算。以计算q(5,3)为例它的递归树会多次计算q(2,2),q(1,1)等子问题。随着n和m增大重复计算的规模呈指数级增长。时间复杂度接近 O(2^(n))完全不可接受。实操心得递归解法是算法设计的“思维草图”。在面试或竞赛中你可以先提出这个思路表明你理解了问题本质但一定要紧接着指出它的效率问题并引出优化方案——记忆化搜索或动态规划。这展示了你的思维深度。3.2 记忆化搜索递归的“备忘录”优化为了避免重复计算最直接的想法是“记住”已经计算过的结果。这就是记忆化搜索Memoization它是自顶向下的动态规划。我们引入一个二维数组或字典memomemo[n][m]用于存储q(n, m)的结果。在递归函数中先查表如果已经计算过直接返回否则进行计算并将结果存入表中再返回。def partition_memo(n, m, memoNone): 使用记忆化搜索计算整数划分数。 if memo is None: # 初始化备忘录用-1表示未计算 memo [[-1] * (m1) for _ in range(n1)] # 先查备忘录 if memo[n][m] ! -1: return memo[n][m] # 边界条件 if n 0 or m 1: return 0 if n 0: memo[n][m] 1 return 1 if n 1 or m 1: memo[n][m] 1 return 1 # 递归计算并保存结果 count partition_memo(n, m-1, memo) partition_memo(n-m, m, memo) memo[n][m] count return count # 测试 result partition_memo(50, 50) # 计算 p(50) print(f“p(50) {result}”)记忆化搜索将时间复杂度降低到了O(n * m)因为每个状态(n, m)最多只计算一次。空间复杂度也是 O(n * m)。对于p(50)这已经可以瞬间计算出结果答案是204226。这是递归思路一个非常实用的优化。3.3 动态规划自底向上的迭代之美动态规划是解决这类重叠子问题、最优子结构问题的标准范式。我们根据递推式从小规模问题开始逐步迭代计算出大规模问题的解。通常使用一个二维DP数组dp[i][j]来表示q(i, j)。算法步骤初始化DP表创建一个(n1) x (n1)的二维数组dp因为m最大为n。初始化dp[0][j] 1对于所有j对应q(0, m)1。确定遍历顺序由于dp[i][j]依赖于dp[i][j-1]同一行左侧和dp[i-j][j]上一行我们可以按行i从1到n或按列j从1到n遍历。按行遍历更直观。状态转移对于每个i从1到n每个j从1到n如果j i意味着允许的最大部分j已经大于当前要划分的数i了那么dp[i][j] dp[i][i]。因为最大部分不可能超过i本身。否则应用递推式dp[i][j] dp[i][j-1] dp[i-j][j]。获取结果最终dp[n][n]就是我们要求的p(n)。def partition_dp(n): 使用动态规划计算整数n的划分数 p(n)。 # 创建DP表dp[i][j] 表示将i划分为最大部分不超过j的划分数 dp [[0] * (n1) for _ in range(n1)] # 初始化对于任何jdp[0][j] 1 for j in range(n1): dp[0][j] 1 # 动态规划填表 for i in range(1, n1): for j in range(1, n1): if j i: # 最大部分j超过i等同于最大部分为i的情况 dp[i][j] dp[i][i] else: # 状态转移方程 dp[i][j] dp[i][j-1] dp[i-j][j] return dp[n][n] # 测试 result partition_dp(100) print(f“p(100) {result}”) # 输出 792070839...一个很大的数这个算法的时间复杂度和空间复杂度都是O(n²)。对于n1000需要约100万次操作和存储在现代计算机上是可以接受的。但如果我们想计算更大的n比如n10000O(n²)的空间1亿个整数可能就会成为瓶颈。3.4 空间优化滚动数组与一维DP观察状态转移方程dp[i][j] dp[i][j-1] dp[i-j][j]你会发现在计算第i行时只依赖于同一行左边的值dp[i][j-1]。第i-j行的值dp[i-j][j]。如果我们按j最大部分从1到n的顺序遍历并且只维护一个一维数组dp[i]表示当前j下各个i的划分数是否可以呢仔细分析dp[i][j-1]就是上一轮j循环中计算出的dp[i]因为我们是按j递增遍历的。而dp[i-j][j]是当前轮次j下已经计算出的dp[i-j]因为i-j i在计算dp[i]时dp[i-j]已经算好了。因此我们可以将二维DP优化为一维DP设dp[i]表示将整数i划分的划分数即p(i)。但这里的递推关系需要改变视角。我们考虑另一种经典的动态规划定义dp[i]表示凑成总和i的方案数每个物品正整数可以无限次使用。这类似于完全背包问题。状态转移dp[i] dp[i - num]其中num遍历所有可能的正整数1, 2, 3, ... i。但这样还是需要两层循环。更巧妙的方法是使用生成函数的思想或者利用五边形数定理但这些属于高级数论范畴。一个更工程化的优化是使用“滚动数组”压缩二维DP。不过对于初学者掌握二维DP并理解其空间优化到一维的思路已经足够。一维完全背包的写法如下def partition_dp_1d(n): 使用一维DP完全背包思路计算整数划分数。 dp[i] 表示凑成整数i的划分方案数。 dp [0] * (n 1) dp[0] 1 # 凑成0的方案数为1空划分 # 遍历“物品”即划分中的加数从1到n for num in range(1, n 1): # 遍历“背包容量”即要凑成的整数i # 必须正序遍历因为每个数字可以无限使用完全背包 for i in range(num, n 1): dp[i] dp[i - num] return dp[n] # 测试 result partition_dp_1d(100) print(f“p(100) {result}”) # 结果应与二维DP一致这个一维DP的时间复杂度依然是 O(n²)但空间复杂度优化到了 O(n)。它从另一个角度完全背包理解了整数划分代码更简洁。但要注意这个解法计算的是p(n)它隐式地包含了所有划分相当于q(n, n)。如果你需要计算q(n, m)最大部分不超过m这个一维形式需要稍作修改外层循环的num只遍历到m即可。4. 算法分析与复杂度探讨4.1 时间复杂度分析对于我们的动态规划解法二维DP两层循环每层最多n次时间复杂度为O(n²)。一维DP外层循环n次内层循环平均约n/2次时间复杂度也是O(n²)。O(n²) 对于 n 在 10⁴ 量级以下是可行的运算次数在 10⁸ 量级现代计算机可在秒级完成。但当 n 达到 10⁵ 或更大时O(n²) 就显得力不从心了。有没有更快的算法有的基于五边形数定理的算法可以在O(n√n)的时间复杂度内计算出 p(n)这对于非常大的 n如 10⁵, 10⁶是必要的。其核心公式是 p(n) p(n-1) p(n-2) - p(n-5) - p(n-7) p(n-12) p(n-15) - ... 其中减号后面的数字是广义五边形数。这个算法将问题复杂度降低了一个数量级但理解和实现起来比动态规划复杂得多。4.2 空间复杂度分析二维DP需要存储 (n1) x (n1) 的矩阵空间复杂度为O(n²)。这是主要的瓶颈。一维DP只需要一个长度为 n1 的数组空间复杂度为O(n)。这是推荐的做法。记忆化搜索最坏情况下需要存储所有状态空间复杂度也是 O(n²)但实际可能由于递归栈和哈希表开销略高。在内存受限的环境中一维DP是首选。如果n极大甚至需要计算 p(n) 对某个大数取模的结果这是竞赛中的常见要求一维DP结合滚动数组思想是标准做法。4.3 递归与递推的思维对比整数划分问题完美展示了算法设计的两种核心思维模式递归自顶向下从大问题出发不断分解为小问题直到触达边界。思维符合人类直觉但容易产生重复计算。记忆化搜索弥补了这一缺陷。递推自底向上从小问题开始逐步推导出大问题的解。动态规划是这种思维的典型体现。它需要更严谨的状态定义和转移方程但效率通常更高也更利于优化。在解决新问题时我个人的习惯是先用递归思路把问题想清楚写出递推关系然后立刻考虑是否能用记忆化搜索优化最后如果对效率有更高要求再尝试转化为迭代的动态规划并考虑空间优化。这个过程能确保你对问题的理解是层层递进的。5. 扩展变体与实战应用整数划分不是一个孤立的算法题它有多种变体并且在其他场景中会换一副“面孔”出现。5.1 常见变体问题限制划分部分个数求将n划分为恰好k个部分的方案数。这对应着p(n, k)。其递推关系为p(n, k) p(n-1, k-1) p(n-k, k)考虑最小部分是否为1。这同样可以用动态规划解决。划分部分互不相同求将n划分为若干互不相同的正整数的方案数。这等价于经典的“子集和”问题或背包问题每个数最多选一次。可以用DP求解状态dp[i][j]表示考虑前i个不同的数凑成总和j的方案数。奇划分划分中的所有部分都是奇数。有趣的是一个数n的奇划分数等于其互不相同的划分数。这是一个经典的组合恒等式。输出具体划分方案不仅计数还要输出所有划分方式。这需要结合回溯法DFS进行搜索并在搜索过程中通过排序例如保证划分序列非递增来去重。5.2 在其他算法问题中的应用整数划分的思想常常隐藏在其他问题中硬币找零问题给定不同面额的硬币无限个和一个总金额求凑成总金额的组合数。这就是整数划分问题一维DP完全背包解法。例如硬币面额为[1,2,5]求凑成5元的组合数。完全平方数问题给定正整数n找到最少的完全平方数如1,4,9,16,...使得它们的和等于n。这可以看作一个特殊的整数划分问题划分的部分被限制在完全平方数集合内并且要求部分数最少。通常用动态规划dp[i] min(dp[i], dp[i - j*j] 1)来解决。分割等和子集给定一个只包含正整数的数组判断是否可以将其分割成两个和相等的子集。这可以转化为一个“是否能用数组中部分数凑成总和一半”的问题是0-1背包问题与整数划分中“部分互不相同”的变体思路相通。5.3 一个实战案例零钱兑换II力扣LeetCode上的第518题“零钱兑换II”就是一个标准的整数划分完全背包问题。题目描述给定不同面额的硬币和一个总金额写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。解法一维DPdef change(amount, coins): :type amount: int :type coins: List[int] :rtype: int dp [0] * (amount 1) dp[0] 1 # 金额为0时有一种组合什么都不选 # 注意这里必须先遍历硬币再遍历金额以保证组合数不考虑顺序 for coin in coins: for i in range(coin, amount 1): dp[i] dp[i - coin] return dp[amount] # 示例硬币面额[1,2,5]总金额5 # 组合有5 221 2111 11111。共4种。 print(change(5, [1,2,5])) # 输出 4关键点为什么外层循环是硬币内层循环是金额这与我们之前计算p(n)的一维DP外层是num内层是i顺序一致。这种顺序保证了我们统计的是“组合数”而不是“排列数”。如果交换循环顺序就会得到考虑顺序的方案数那就不符合整数划分“不考虑顺序”的定义了。这是此类问题一个非常容易出错的地方。避坑技巧在解决“组合数”类完全背包问题时牢记“物品硬币在外容量金额在内”的循环顺序。如果想求“排列数”则需要交换循环顺序。这个细微差别直接决定了答案的正确性务必在理解的基础上记忆。6. 调试、测试与性能考量6.1 如何验证算法正确性对于整数划分这种计数问题验证算法正确性至关重要。小规模手工验证对于n1到10手工计算或查阅已知数列OEIS A000041进行比对。这是第一步。交叉验证用递归记忆化、二维DP、一维DP三种方法实现对同一个n计算结果看是否一致。利用数学性质例如p(n)的增长速度很快可以用近似公式如哈代-拉马努金公式估算数量级看计算结果是否合理。单元测试编写测试用例包含边界情况n0, n1和常规情况。6.2 大数处理与溢出问题p(n)增长极快。p(100)约等于2.0e8p(200)就超过了3.9e12。在C或Java中使用int或long类型很快就会溢出。对策如果题目要求精确值必须使用大整数库如Python的intJava的BigInteger。更常见的情况许多编程题要求结果对一个模数如10^97取余。这时我们可以在动态规划的状态转移中每一步都进行取模运算dp[i] (dp[i] dp[i - num]) % MOD。这能保证结果在整数范围内同时考验你对模运算加法的理解。6.3 性能优化实战当n很大时例如 n10^5即使 O(n²) 的DP也无法承受。此时需要考虑 O(n√n) 的五边形数定理算法。其Python实现示例如下def pentagonal_num(k): 返回第k个广义五边形数 return k * (3 * k - 1) // 2 def partition_fast(n, MODNone): 使用五边形数定理计算p(n)可选取模。 partitions [0] * (n 1) partitions[0] 1 for i in range(1, n 1): k 1 while True: pent pentagonal_num(k) if pent i: break # 根据公式符号为 (-1)^(k-1) sign -1 if (k - 1) % 2 else 1 partitions[i] sign * partitions[i - pent] # 处理负的广义五边形数 pent pentagonal_num(-k) if pent i: break partitions[i] sign * partitions[i - pent] # 注意这里sign相同因为(-k)的指数是k k 1 if MOD: partitions[i] % MOD return partitions[n] if not MOD else partitions[n] % MOD # 测试计算p(1000)模 1000000007 result partition_fast(1000, 1000000007) print(f“p(1000) mod 10^97 {result}”)这个算法的时间复杂度约为 O(n√n)因为内层循环的k大约增长到√n量级。对于n10^5运算量在千万级是可行的。注意这个算法直接计算的是p(n)不能直接用于计算q(n, m)。6.4 内存与时间的权衡在工程实践中我们需要根据问题规模和要求进行权衡n较小5000使用一维DP代码简单效率足够。n中等5000~20000一维DP可能接近时间极限如竞赛环境需确保代码高效避免不必要的操作。n很大50000且需精确值必须使用五边形数定理等高级算法。只需结果对MOD取模一维DP结合取模运算是通用且安全的选择适用于大多数在线判题场景。最后分享一个我调试此类问题时的心得一定要从n0,1,2开始打印出整个DP表肉眼观察数值的变化是否符合你的递推逻辑。对于二维DP画表格对于一维DP打印数组。这比任何调试器都更能帮你直观地发现状态转移中的错误尤其是边界条件和循环顺序的错误。整数划分的递推关系看似简单但下标处理稍有不慎就会满盘皆输耐心地手动模拟前几步是写出正确代码最可靠的保障。