1. 从一道经典面试题说起整数划分到底是什么如果你刷过一些算法题或者上过《算法设计与分析》这门课大概率会碰到“整数划分”这个问题。我第一次遇到它是在准备一场技术面试时题目描述很简单“给定一个正整数n将其表示为一系列正整数之和求有多少种不同的表示方法划分方式”。例如整数4可以划分为43 12 22 1 11 1 1 1 一共是5种。看起来是不是有点像“凑零钱”或者“背包问题”确实它们在动态规划的思想上有相通之处但整数划分问题本身有更独特的组合数学背景和多种分析视角是理解递归、动态规划乃至生成函数的一个绝佳样板。这个问题之所以经典是因为它剥离了具体业务的外衣直指算法设计的核心如何将一个看似复杂的计数问题通过巧妙的定义和状态转移转化为计算机可以高效求解的模型。它不涉及复杂的数据结构却对思维抽象能力要求很高。今天我们就来彻底拆解这个问题不仅会给出从暴力递归到优化动态规划的多种解法更会深入分析其时间复杂度的来龙去脉并探讨如何运用主定理进行严谨的算法分析。无论你是正在备考的学生还是希望夯实算法基础的开发者相信这篇来自一线实践的经验总结都能给你带来收获。2. 问题定义与核心思路拆解两种不同的“视角”决定了解法在动手写代码之前我们必须先明确问题。整数划分问题实际上有多种变体最常见的两种定义是考虑顺序的划分将n划分成若干个正整数之和划分方式31和13被视为不同的划分。这通常对应“完全背包”模型。不考虑顺序的划分也就是我们开头举的例子31和13被视为同一种划分。这是我们本次讨论的重点也是组合数学中更经典的“分拆数”问题Partition Function。我们聚焦于第二种定义。求解这个问题的核心难点在于如何“不重不漏”地枚举所有划分。一个直观但低效的想法是递归地枚举每个加数。比如对于n4第一个加数可以是1,2,3,4然后对剩余部分继续划分。但这会产生大量重复例如从“第一个加数选1剩余3划分为21”和“第一个加数选2剩余2划分为11”最终都得到了121这个无序组合。因此我们需要一个更聪明的状态定义来避免重复。这里引出两个最关键、也最常用的思路2.1 思路一基于“最大加数”的递归定义这是最符合人类直觉的建模方式。我们定义f(n, m)表示将整数n划分为最大加数不超过m的所有划分方式的数量。边界条件f(0, m) 1表示已经分完算一种划分f(n, 0) 0n0时没有加数可用无法划分。状态转移考虑当前最大加数m在划分中是否出现。划分中不包含m那么所有加数都小于m即问题转化为f(n, m-1)。划分中包含至少一个m那么我们可以先拿出一个m剩下的总和是n-m并且划分中最大加数仍然可以包含m因为还可以继续用m即问题转化为f(n-m, m)。递推关系f(n, m) f(n, m-1) f(n-m, m)其中需要保证n m。若n m则f(n, m) f(n, n)因为最大加数不可能超过n本身。我们要求的答案就是f(n, n)。这个定义的精妙之处在于它通过限制“最大加数”这个维度天然地保证了划分的不重复性。所有划分都被唯一地归类到某个最大加数下。2.2 思路二基于“物品无限”的完全背包模型如果你熟悉动态规划会发现整数划分问题可以转化为一个特殊的“完全背包”问题有一个容量为n的背包物品的体积分别是1, 2, 3, ..., n每种物品有无限个求恰好装满背包的方案数。这里的“体积”就是加数的大小“方案数”就是划分方式的数量。定义dp[i]表示凑成总和为i的方案数。初始化dp[0] 1凑出0只有一种方案什么都不选。然后我们遍历“物品”即加数j从1到n对于每个j更新容量i从j到n的dp值dp[i] dp[i - j]。这个更新的含义是对于当前总和i所有包含了加数j的方案都可以由i-j的方案加上一个j得到。注意这个遍历顺序先遍历物品j再遍历容量i是关键。它保证了在考虑物品j时dp[i-j]中可能已经包含了物品j从而实现了物品的无限取用完全背包。同时这个顺序也固定了物品的考虑顺序总是先考虑小数字从而避免了12和21被算作两种方案实现了无序划分。两种思路最终是等价的但思考角度不同。第一种更贴近问题本身的组合数学特性第二种则将其纳入了更广泛的动态规划框架中便于我们利用已知的算法模板。3. 核心算法实现与细节剖析理解了思路我们来看具体的代码实现。我会分别展示递归、记忆化搜索和动态规划三种写法并分析其中的细节和陷阱。3.1 递归与记忆化搜索实现基于思路一我们可以直接写出递归函数。def partition_recursive(n, m): 返回将n划分为最大加数不超过m的划分方式数递归版本。 # 边界条件 if n 0: return 1 if m 0 or n 0: return 0 # 如果最大加数超过n则等价于最大加数为n if m n: return partition_recursive(n, n) # 状态转移不包含m 包含至少一个m return partition_recursive(n, m-1) partition_recursive(n-m, m) # 计算整数4的划分数 print(partition_recursive(4, 4)) # 输出5这个递归实现非常简洁直接对应了我们的数学定义。但是它的效率极低存在大量的重复子问题计算。例如计算f(4,4)会递归调用到f(3,3),f(2,2)等而这些子问题又会被多次计算。为了解决重复计算我们引入记忆化搜索Memoization即用一个缓存字典或数组来存储已经计算过的f(n, m)结果。def partition_memo(n, m, memoNone): 返回将n划分为最大加数不超过m的划分方式数记忆化搜索版本。 if memo is None: memo {} # 检查缓存 if (n, m) in memo: return memo[(n, m)] # 边界条件 if n 0: return 1 if m 0 or n 0: return 0 # 如果最大加数超过n则等价于最大加数为n if m n: result partition_memo(n, n, memo) else: # 状态转移 result partition_memo(n, m-1, memo) partition_memo(n-m, m, memo) # 存储结果到缓存 memo[(n, m)] result return result print(partition_memo(4, 4)) # 输出5记忆化搜索将时间复杂度从指数级降低到了O(n^2)因为总共有n * n个状态需要计算每个状态的计算是常数时间。这是递归问题优化的标准操作。3.2 动态规划实现我们更常用的是自底向上的动态规划它更直观且通常有更好的常数性能。这里分别展示基于思路一和思路二的DP表格。方法A基于“最大加数”的二维DP我们创建一个二维数组dp[n][m]其中dp[i][j]表示将整数i划分为最大加数不超过j的方案数。def partition_dp_2d(n): 使用二维DP计算整数n的划分数。 # 初始化一个 (n1) x (n1) 的二维数组所有元素为0 dp [[0] * (n 1) for _ in range(n 1)] # 初始化边界条件dp[0][j] 1 for all j for j in range(n 1): dp[0][j] 1 # 动态规划填表 for i in range(1, n 1): # i 代表要划分的整数 for j in range(1, n 1): # j 代表当前允许的最大加数 if j i: # 最大加数超过i等同于最大加数为i dp[i][j] dp[i][i] else: # 状态转移方程dp[i][j] dp[i][j-1] dp[i-j][j] dp[i][j] dp[i][j-1] dp[i-j][j] return dp[n][n] print(partition_dp_2d(4)) # 输出5方法B基于“完全背包”的一维DP这是更简洁、空间效率更高的方法也是面试中最常考的写法。def partition_dp_1d(n): 使用一维DP完全背包模型计算整数n的划分数。 dp [0] * (n 1) dp[0] 1 # 总和为0的方案数为1 # 遍历“物品”即可能的加数 for j in range(1, n 1): # 遍历“背包容量”即要凑成的总和 for i in range(j, n 1): dp[i] dp[i - j] return dp[n] print(partition_dp_1d(4)) # 输出5实操心得对于初学者我强烈建议先从二维DP的思路一开始理解因为它直接对应了问题的原始定义逻辑清晰。当你完全理解后再过渡到一维DP的写法。一维DP的代码虽然短但其中“先遍历物品再遍历容量”的顺序是精髓也是容易出错的地方。如果顺序颠倒先遍历容量再遍历物品得到的就是考虑顺序的划分数量了结果会大很多。3.3 算法复杂度分析我们来详细分析一下上述算法的时间和空间复杂度这是算法分析的核心。朴素递归时间复杂度是指数级的O(2^n)量级因为递归树近似于二叉树深度为n。完全不可用于稍大的n如n30就可能非常慢。记忆化搜索总共需要计算的状态数是O(n^2)个因为n和m都在[0, n]范围内。每个状态的计算是常数时间两次查表或递归调用。因此时间复杂度为 O(n²)。空间复杂度也是O(n²)用于存储记忆化表格。二维动态规划我们显式地填充了一个(n1) x (n1)的表格每个格子计算一次。时间复杂度为 O(n²)空间复杂度为 O(n²)。一维动态规划外层循环j从1到n内层循环i从j到n。循环总次数大约是n (n-1) ... 1 n(n1)/2所以时间复杂度依然是 O(n²)。但是空间复杂度优化到了 O(n)这是它的主要优势。可以看到通过动态规划我们将一个指数级的问题优化到了多项式级别O(n²)。对于n在几千以内的规模这个算法都是非常高效的。4. 算法分析进阶时间复杂度与主定理的应用对于递归算法我们如何严谨地分析其时间复杂度呢这就引出了《算法设计与分析》课程中的一个重要工具——主定理Master Theorem。它提供了一种“菜谱式”的方法用于求解形式为T(n) aT(n/b) f(n)的递归式的时间复杂度。虽然我们的整数划分递归式不完全符合这种形式但我们可以通过分析来加深理解。我们的递归函数partition_recursive的调用树并不均衡不符合T(n/b)的形态。它的递归式更接近T(n, m)依赖于T(n, m-1)和T(n-m, m)这是一个二维的递推难以直接套用主定理。但是我们可以分析一个简化版的问题如果只考虑最坏情况下的递归调用次数。在最坏情况下例如m始终不大于n每次调用产生两个子调用递归深度约为n因此调用次数上界约为O(2^n)。这是一个非常粗略的估计也印证了朴素递归不可行。主定理的真正用武之地是在分析那些分治算法时比如归并排序、快速排序、二分查找等。例如归并排序的递归式为T(n) 2T(n/2) O(n)。根据主定理a 2,b 2,f(n) O(n)。计算n^(log_b a) n^(log_2 2) n^1 n。比较f(n) O(n)与n^(log_b a) O(n)发现两者渐进相同即f(n) Θ(n^(log_b a))。对应主定理的情况二因此时间复杂度T(n) Θ(n^(log_b a) * log n) Θ(n log n)。经验技巧虽然整数划分的递归式不直接适用主定理但理解主定理能帮你建立分析递归算法复杂度的框架思维。当你设计出一个递归算法时首先问自己子问题规模是否以固定比例缩小n/b子问题数量是否固定a合并子问题的代价是多少f(n)如果符合直接套主定理如果不符合就要像我们上面做的那样通过分析递归树或猜测归纳法来推导。对于我们的动态规划解法其复杂度分析更直接就是计算状态数量乘以每个状态的计算代价。二维DP有O(n²)个状态每个状态O(1)计算所以是O(n²)。这是比主定理更简单的循环累加分析。5. 扩展、变体与实战中的坑掌握了基础问题我们来看看它的几个常见变体以及在实战中容易踩的坑。5.1 变体一输出具体的划分方案有时题目不仅要求数量还要求输出所有划分本身。这需要我们在动态规划记录方案数的同时回溯出具体路径。def get_partitions(n): 返回整数n的所有划分方案列表。 使用回溯法。 def backtrack(remaining, start, current_path, result): remaining: 剩余需要划分的数 start: 当前可用的最小加数为了避免重复划分要求非递减即[2,1,1]不会出现只有[1,1,2] current_path: 当前已选择的加数列表 result: 存储所有结果的列表 if remaining 0: result.append(current_path[:]) # 找到一种划分复制并保存 return for i in range(start, remaining 1): current_path.append(i) backtrack(remaining - i, i, current_path, result) # 注意start传i保证非递减 current_path.pop() # 回溯 result [] backtrack(n, 1, [], result) return result print(get_partitions(4)) # 输出[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]注意事项在回溯生成具体方案时必须定义一个“顺序”来避免重复。这里我们通过start参数强制要求划分中的加数序列是非递减的即后一个加数不小于前一个。这是生成无序组合的常用技巧。如果允许任意顺序你会得到大量重复的排列。5.2 变体二限制划分的个数或加数的范围限定划分的个数例如将n恰好划分为k个正整数之和的方案数。这需要增加一个状态维度。定义dp[i][j]为将i划分为j个正整数的方案数。可以考虑第一个数字是1还是大于1来推导转移方程dp[i][j] dp[i-1][j-1] dp[i-j][j]前提ij。其含义是如果第一个数是1则剩下i-1需要分成j-1份如果所有数都大于1那么我们可以给每个数先减去1总和变为i-j仍然分成j份。限定加数的范围例如只能用1, 3, 5这些特定的数来划分。这就变成了一个标准的“完全背包”问题物品集合是给定的特定数字。代码上只需修改遍历“物品”的集合即可。5.3 实战踩坑点初始化陷阱在一维DP的完全背包写法中dp[0] 1是灵魂。它表示凑出总和0有一种方案什么都不选。如果错误地初始化为0结果将永远是0。循环顺序陷阱再次强调一维DP中必须先遍历物品加数再遍历背包容量总和。如果反过来计算的就是排列数考虑顺序的划分而不是组合数。你可以用n3测试一下正确结果无序是3种3, 21, 111错误顺序会得到4种多出一个12。数值溢出问题整数划分的数量随着n增大会爆炸式增长。例如p(100)已经超过1亿。在编程时如果题目要求返回具体数字要留意是否需要对结果取模常见于算法竞赛。dp数组应使用能容纳大整数的类型如Python的intC的long long。理解状态定义二维DP的dp[i][j]中j是“最大加数不超过j”而不是“恰好以j结尾”。这是理解转移方程dp[i][j] dp[i][j-1] dp[i-j][j]的基础。第一个项dp[i][j-1]很容易被漏掉。6. 性能优化与不同场景下的选择虽然O(n²)的DP算法对于大多数应用已经足够但当n非常大例如n 5000时我们可能需要更优的算法。整数划分数p(n)有著名的五边形数定理和欧拉生成函数可以用于计算更大的n。不过这些属于组合数学的深水区面试和一般应用中较少涉及。在实际工程或面试中你需要根据场景做出选择只需结果数量n中等 5000使用一维DP代码简洁空间效率高。需要输出所有具体方案使用回溯法。注意其时间复杂度是指数级的n不能太大通常n30比较安全。问题有额外约束如划分个数k增加DP的状态维度设计对应的转移方程。作为更大问题的一个子模块确保你的DP函数被良好封装和记忆化避免重复计算。整数划分问题就像算法世界里的一个“麻雀”虽小但五脏俱全。它串联起了递归、记忆化、动态规划、状态设计、背包模型、回溯算法等多个核心知识点。通过彻底吃透这个问题你收获的不仅仅是一道题的解法更是一套分析和解决复杂计数问题的思维框架。下次当你遇到类似“有多少种方式”的问题时不妨先想想能不能定义一个清晰的状态能不能找到子问题之间的递推关系这往往是破题的关键。