P1025 [NOIP2001 提高组] 数的划分 题解复盘 基本信息 项目 内容 题目编号、来源 P1025 洛谷 / [NOIP2001 提高组] 数的划分 训练层级 B DFS + 剪枝 知识版块 DFS、剪枝、组合枚举
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：把整数 n 分成 k 份，每份 ≥ 1，求方案数（顺序无关）；约束 ：n ≤ 200，k ≤ 6；底层结构 ：组合枚举 + 剪枝优化。数据规模 n ≤ 200，k ≤ 6，DFS + 剪枝完全可行。 候选算法和依据 DFS + 剪枝；依据 ：把问题转化为「从 1~n 中选 k 个可重复的数，使和为 n，且不下降」，这是组合枚举的变种，用 start 参数保证不下降。 复杂度预判 时间复杂度 O(C(n+k-1, k))，k ≤ 6 剪枝后很小；空间复杂度 O(k)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 第一步定义dfs(step, start, sum)，step 表示已经选了几个数，start 表示当前可以从哪个数开始选（保证不下降），sum 表示当前总和；第二步如果step == k，检查sum == n，若成立则 ans++；第三步枚举 i 从 start 到 n，用剪枝sum + i * (k - step) <= n跳过不可能的分支；第四步递归dfs(step + 1, i, sum + i)。核心思想 ：把“划分”转化为“选 k 个可重复的数，使和为 n，且不下降”，用 DFS 枚举所有组合，剪枝优化。 错因回溯 1. 把问题想成排列，导致重复计算（如 1,1,5 和 1,5,1 算成两种）；2. 没有剪枝导致超时；3. 递归出口写成step > k，从 1 开始，和从 0 开始搞混；4.start传递错误，写成start + 1而不是i（因为允许重复选同一个数）。 边界和易错点 1. 顺序无关，所以要保证不下降（start参数）；2. 同一个数可以选多次，所以递归时start传i而不是i+1；3. 剪枝条件sum + i * (k - step) <= n：如果从 i 开始，后面全取最小值 i 都已经超过 n，直接 break；4. k 最大 6，但 n 最大 200，剪枝后很快。 下次看到什么信号，我应该想到这个方法 看到「把 n 分成 k 份 + 顺序无关 + 求方案数 」，DFS + 剪枝 或 DP。
AC 完整代码 # include <iostream> # include <algorithm> # include <iomanip> # include <vector> using namespace std; int n, k; int ans; void dfs ( int step, int start, int sum) { if ( sum> n) return ; if ( step== k) { if ( sum== n) ans++ ; return ; } for ( int i= start; i<= n; i++ ) { if ( sum+ i* ( k- step) > n) break ; dfs ( step+ 1 , i, sum+ i) ; } } int main ( ) { cin>> n>> k; dfs ( 0 , 1 , 0 ) ; cout<< ans; return 0 ; } 