蓝桥杯算法精讲：整数划分问题的DFS回溯与动态规划解法

1. 从一道“简单”的蓝桥杯真题说起加法分解的陷阱如果你正在准备蓝桥杯或者对算法竞赛感兴趣那么“加法分解”这类题目你一定不陌生。乍一看题目描述往往很简单给定一个正整数N要求找出所有将其表示为若干个正整数之和的方案并且这些正整数需要满足某种特定的顺序比如递增、递减或限制条件比如不能重复、个数固定。ALGO-645这道题就是这类问题的典型代表。很多新手看到题目第一反应可能就是“这不就是回溯吗写个DFS从1开始尝试加加到等于N就记录一条路径。”思路没错但如果你真这么写提交上去很可能不是超时就是答案错误。这就是算法题里常见的“陷阱”题目描述越简单背后对算法效率和思维严谨性的要求往往越高。“加法分解”远不止是暴力枚举所有组合那么简单。它本质上是一个经典的整数划分问题是组合数学和动态规划领域的核心课题。处理不当当N稍微大一点比如50你的程序可能就会因为方案数爆炸整数划分数是指数级增长的而彻底卡死。所以今天我们不只讲这道题怎么写更要拆解清楚面对一个看似“无序”的加法分解问题我们该如何系统性地分析、设计算法并避开所有常见的坑。这对于你理解回溯的剪枝、动态规划的状态设计乃至数学思维在算法中的应用都至关重要。2. 问题本质剖析整数划分与“无序性”的约束在深入代码之前我们必须先吃透题意。题目编号ALGO-645关键词是“加法分解”和“无序阶段”。这里的“无序”是整个问题的关键约束也是容易产生误解的地方。2.1 什么叫做“无序”的加法分解举个例子假设 N4。如果考虑“有序”分解即顺序不同的序列视为不同方案那么分解方式有 1111, 112, 121, 211, 22, 13, 31, 4 一共8种。但如果题目要求是“无序”分解那么顺序不同的相同数字组合被视为同一种方案。此时我们只关心组合本身不关心顺序。通常为了消除顺序的影响我们会强制规定分解出的数字序列是非降序递增或相等或非升序递减或相等的。这是处理无序组合问题的标准手法。对于N4其无序划分非降序为 4 31 22 211 1111 一共5种。可以看到112、121和211被合并为一种211。2.2 问题建模搜索树与状态定义我们的目标是生成所有满足非降序条件的加法组合。最直观的方法是深度优先搜索DFS回溯。我们如何定义搜索状态一个核心状态是当前正在构造的分解序列path以及当前序列中所有数字的和current_sum。为了满足“非降序”条件我们还需要一个状态当前可以选取的数字的最小值start。这个start参数是保证生成序列不重复指组合意义下的精髓。为什么需要start参数假设我们正在构造序列上一个加入的数字是x。为了确保下一个数字不小于x非降序我们在下一层递归中只能从x开始尝试选取数字。这避免了生成像[2, 1]这样的序列因为12违反了非降序从而保证了每一种数字组合只以其“最小字典序”的形式即非降序排列被生成一次。因此DFS函数的签名可以设计为dfs(int remain, int start, vectorint path)。remain: 距离目标N还差多少。start: 当前可以尝试的数字的最小值。path: 当前已构造的序列。2.3 递归边界与剪枝策略递归的边界条件很清晰成功边界当remain 0时说明当前path的和恰好为N我们找到了一组有效划分将其存入结果集。失败边界当remain 0时说明当前路径的和已经超过N此路径无效直接返回。剪枝边界这是一个重要的优化。在循环尝试数字i时如果i remain那么即使选择i剩余的数字remain - i也会变成负数后续无论如何也无法凑成N。因此我们可以提前终止循环。更进一步的如果我们要求分解出的数字个数至少为k个还可以根据剩余深度和最小数字进行剪枝但本题未明确要求个数。3. 核心算法实现DFS回溯与细节处理理解了状态定义我们就可以动手实现代码了。这里以C为例给出清晰的实现和逐行解读。#include iostream #include vector using namespace std; vectorvectorint result; // 存储所有划分方案 vectorint path; // 当前路径 // DFS回溯函数 // remain: 还需要凑的和 // start: 当前可以选取的数字的最小值为了保证非降序 void dfs(int remain, int start) { // 边界条件1找到一组有效划分 if (remain 0) { result.push_back(path); return; } // 边界条件2当前和已超过N路径无效 // 这个判断其实可以被循环内的条件替代但放在这里更清晰 // if (remain 0) return; // 从start开始尝试直到remain因为i不能大于剩余值 for (int i start; i remain; i) { // 选择数字 i path.push_back(i); // 递归剩余值为 remain-i下一层最小数字从i开始保证非降序 dfs(remain - i, i); // 回溯撤销选择 path.pop_back(); } } int main() { int N; // 假设从标准输入读取N cin N; // 初始状态需要凑齐N最小可以从1开始选 dfs(N, 1); // 输出所有方案 for (const auto p : result) { for (size_t j 0; j p.size(); j) { cout p[j]; if (j ! p.size() - 1) cout ; } cout endl; } return 0; }代码关键点解析dfs(N, 1)的初始调用表示我们要对整数N进行划分并且第一个数字至少可以从1开始选。循环条件i remain这是最重要的剪枝。它确保了每次尝试的数字i都不会导致剩余值remain-i为负。例如当remain2时i只能取1或2取3就直接跳过了。递归调用dfs(remain - i, i)这里传递的第二个参数是i而不是start。这就是实现“非降序”的核心。它告诉下一层递归“你现在至少要从i开始选数字”从而避免了选择比前一个数字小的数。回溯操作path.pop_back()在递归返回后必须将当前尝试的数字i从路径中移除以便尝试下一个可能的数字i1。这是回溯算法的标准步骤。注意输出格式。蓝桥杯的题目对输出格式要求极其严格。上述代码的输出是每行一个划分数字用‘’连接。务必仔细阅读题目描述确认是否需要输出划分方案数、是否需要特定的顺序如字典序、以及连接符是什么。有时题目要求先输出方案数再输出具体方案。4. 从DFS到动态规划计算划分总数上面的DFS算法可以找到所有具体的划分方案。但有时候题目可能只要求输出划分的总数而不需要具体方案例如N比较大时输出所有方案不现实。这时DFS虽然可以计数但效率可能依然不够高。我们需要更高效的算法——动态规划DP。4.1 DP状态定义定义dp[i][j]为使用不大于j的正整数来构成总和为i的“无序”划分方案数。 这里“不大于j”这个限制是另一种保证“无序性”或者说控制数字选择范围的方式它最终能帮助我们导出经典的转移方程。4.2 状态转移方程推导考虑如何得到dp[i][j]。对于总和i我们考虑划分中是否包含数字j划分中包含至少一个j那么我们可以先放一个j剩下的总和是i-j。对于剩下的部分我们仍然可以使用不大于j的数字因为序列非降序下一个数字可以等于j。所以这部分方案数对应dp[i-j][j]。划分中不包含j那么划分中的所有数字都小于j即不大于j-1。所以这部分方案数对应dp[i][j-1]。因此状态转移方程为dp[i][j] dp[i][j-1] dp[i-j][j] 其中i j。 如果i j那么j根本不可能被使用所以dp[i][j] dp[i][j-1]。4.3 边界条件与初始化dp[0][j] 1总和为0只有一种划分方案就是什么都不选一个空集。这对所有j都成立。dp[i][0] 0(i0)不允许使用任何正整数自然无法组成正数和。4.4 DP代码实现#include iostream #include vector using namespace std; int countPartitions(int N) { // dp[i][j]: 用不大于j的数凑成i的方案数 vectorvectorlong long dp(N 1, vectorlong long(N 1, 0)); // 初始化总和为0的方案数为1 for (int j 0; j N; j) { dp[0][j] 1; } for (int i 1; i N; i) { for (int j 1; j N; j) { if (i j) { // 包含j 不包含j dp[i][j] dp[i][j-1] dp[i-j][j]; } else { // i jj用不上 dp[i][j] dp[i][j-1]; } } } // dp[N][N] 就是用不大于N的数即所有正整数凑成N的方案数 return dp[N][N]; } int main() { int N; cin N; cout countPartitions(N) endl; return 0; }这个DP算法的时间复杂度是O(N²)空间复杂度也是O(N²)。当N达到几百甚至上千时它比枚举所有方案的DFS要高效得多。如果需要还可以优化空间为一维数组。5. 常见“坑点”与实战调试技巧即使理解了算法在实现时依然会踩坑。下面是我在刷题和教学中总结的几个高频问题。5.1 去重失败忘记控制“非降序”这是最常见的错误。如果你在DFS中递归调用时第二个参数传递的是start而不是i就会生成大量重复的组合。// 错误写法会导致重复如[1,2]和[2,1]都被生成 void dfs_wrong(int remain, int start) { if (remain 0) { result.push_back(path); return; } for (int i start; i remain; i) { path.push_back(i); dfs_wrong(remain - i, start); // 错误这里应该传 i path.pop_back(); } }调试方法用一个小N如5手动模拟或打印递归树观察start参数的变化。你会发现错误的写法中下一层递归仍然从很小的数字开始尝试破坏了有序性。5.2 输出格式错误蓝桥杯的评测机是严格比对输出的。常见错误包括行末空格或换行最后一行是否也需要换行通常需要。避免在数字后面多打空格。‘’号处理在拼接字符串输出时容易在最后一个数字后面也输出‘’。使用条件判断if (j ! path.size() - 1)来避免。顺序问题题目可能要求按字典序输出。我们的DFS由于使用了start参数并从小到大尝试生成的路径天然就是非降序排列的这通常符合字典序要求。但务必确认题目描述。5.3 性能问题与优化当N增大时纯粹的DFS可能会超时。剪枝i remain是最基本的剪枝。如果题目要求分解出的数字个数为k还可以加入更强大的剪枝如果path中已有个数加上剩余数字的最小可能个数ceil(remain / i)都大于k或者最大可能个数remain即全1都小于k则可以提前返回。记忆化搜索对于只求总数的DP问题DFS也可以结合记忆化。状态可以定义为(remain, start)表示从start开始凑remain的方案数。但要注意这个状态定义下start是“最小值”与之前求具体方案的DFS状态意义一致可以用于记忆化计数。5.4 整数溢出在DP计算方案数时N稍微大一点比如100划分总数就可能是一个巨大的数字远超int范围。务必使用long long来存储DP数组和结果。6. 举一反三算法思想的延伸应用解决“加法分解”问题所锻炼的思维能应用到许多其他场景。6.1 组合问题建模许多组合问题都可以转化为类似的“选取”模型。例如零钱兑换问题求方案数给定不同面额的硬币和一个总金额求凑成总金额的硬币组合数。这几乎就是整数划分的变体只是“数字”变成了固定的硬币面额集合。状态定义dp[i]表示凑成金额i的方案数转移方程为dp[i] dp[i - coin]。子集和问题给定一个正整数集合和一个目标和判断是否存在子集的和等于目标。这可以看作是一种特殊的、只判断是否存在的“划分”。6.2 搜索中的顺序控制“非降序”这个技巧是解决组合无序类搜索问题的通用钥匙。与之相对的是排列有序问题在排列问题中我们通常使用一个visited数组来标记哪些元素已被使用而不需要start参数。清晰地辨别问题是求组合还是排列是正确设计搜索参数的第一步。6.3 动态规划的状态设计思维从求具体方案的DFS到求方案总数的DP我们看到了两种不同需求下的算法选择。DP的dp[i][j]状态设计使用不大于j的数凑成i非常巧妙。它通过限制数字的上限自然地避免了顺序问题将一个涉及“序列”的问题转化为了一个纯粹的“计数”问题。这种“通过增加状态维度来满足约束条件”的思想在解决复杂的DP问题时非常有用例如背包问题中的“恰好装满”、“限制物品个数”等条件都可以通过增加DP数组的维度来实现。最后关于这道ALGO-645虽然我没有官方的题目描述原文但基于“加法分解”和“无序阶段”的典型含义以上的分析和代码已经覆盖了其核心考点。在实战中请务必以题目给出的具体输入输出格式为准。算法的学习正是通过这样一道道题目的深入剖析积累起对状态、转移、边界和优化的敏感度。下次再遇到“分解”、“划分”、“组合”这类关键词时希望你脑海中能立刻浮现出start参数和dp[i][j]的方程。