别再死磕DP了！用DFS+剪枝5分钟搞定‘数的划分’（洛谷P1025/NOIP真题）-开发者社区

暴力美学：用DFS+剪枝优雅解决‘数的划分’问题

在算法竞赛中，动态规划(DP)常常被视为解决组合优化问题的"银弹"。但当我们面对NOIP真题《数的划分》这类经典问题时，是否一定要死磕状态转移方程呢？实际上，对于数据范围较小的情况（如n≤200），深度优先搜索(DFS)配合精心设计的剪枝策略，往往能以更直观的代码结构和更短的开发时间，交出令人满意的答卷。

1. 重新认识‘数的划分’问题

数的划分问题要求将正整数n拆分成k个正整数之和的方案数，顺序不同但组合相同的视为同一种方案。例如，将7分成3份有4种分法：1+1+5、1+2+4、1+3+3和2+2+3。

传统DP解法需要构建二维状态数组dp[i][j]，表示将i划分为j个数的方案数。状态转移方程为：

dp[i][j] = dp[i-1][j-1] + dp[i-j][j]

虽然数学上很优美，但对初学者来说，理解这个递推关系需要较强的抽象思维能力。相比之下，DFS的暴力搜索思路更加符合人类直觉——我们只需要枚举所有可能的组合，然后统计符合条件的解。

在算法竞赛中，当n≤200且时间限制宽松时（如1秒），DFS+剪枝往往比DP更容易快速实现且不易出错。

2. DFS解法核心框架

基础的DFS思路非常简单：从1开始尝试每个可能的数字，递归地构建划分序列。但这样的纯暴力搜索时间复杂度高达O(n^k)，完全无法承受。我们需要两个关键剪枝策略来优化：

2.1 升序枚举避免重复

为了保证不重复计数，我们可以强制要求划分序列是非递减的。这意味着每次选择的数字不小于前一个数字。这样，1+2+4和2+1+4被视为同一种方案，只会被计数一次。

void dfs(int remaining, int parts, int start) { if (parts == 0) { if (remaining == 0) count++; return; } for (int i = start; i <= remaining; i++) { dfs(remaining - i, parts - 1, i); } }

2.2 可行性剪枝大幅提速

更聪明的剪枝来自数学观察：如果剩余需要划分的数是d，还需要选择p个数，那么当前选择的数i必须满足i×p ≤ d。因为后续的p个数每个至少为i，它们的和至少是i×p。

for (int i = start; i * parts <= remaining; i++) { dfs(remaining - i, parts - 1, i); }

这个剪枝条件能将搜索空间缩小几个数量级。例如，在划分n=200,k=10时，纯暴力搜索需要约200^10次操作，而优化后实际递归调用次数可能只有几千次。

3. 算法性能分析与对比

让我们通过具体数据来比较不同方法的效率：

方法	时间复杂度	n=20,k=5用时	代码复杂度	易调试性
标准DP	O(n×k)	<1ms	高	中
DFS+基础剪枝	O(n^k)	约50ms	中	高
DFS+双重剪枝	实际远低于O(n^k)	<1ms	低	很高

虽然DP的理论时间复杂度最优，但在实际竞赛中，DFS+剪枝有以下优势：

编码速度快：熟练选手可以在5分钟内完成
不易出错：状态转移方程容易写错边界条件
空间效率高：不需要存储二维DP表
可扩展性强：容易修改以输出具体划分方案

4. 竞赛实战技巧与变种

在NOIP等竞赛中，遇到类似问题时可以考虑以下策略：

数据范围优先：当n≤200时，DFS+剪枝通常是安全选择
剪枝设计原则：
- 优先考虑数学性质剪枝（如i×p≤d）
- 其次考虑对称性剪枝（如升序枚举）
- 最后考虑最优性剪枝（如当前和已超过n）
常见变种问题：
- 允许空划分（转化为n+k划分为k个正数）
- 限制划分元素大小（调整i的枚举范围）
- 求具体划分方案（在DFS中记录路径）

// 输出所有划分方案的增强版DFS void dfs(int d, int p, int st, vector<int>& path) { if (p == 0) { if (d == 0) { for (int num : path) cout << num << " "; cout << endl; } return; } for (int i = st; i * p <= d; ++i) { path.push_back(i); dfs(d - i, p - 1, i, path); path.pop_back(); } }