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>usingnamespacestd;intn,k;intans;voiddfs(intstep,intstart,intsum){if(sum>n)return;if(step==k){if(sum==n)ans++;return;}for(inti=start;i<=n;i++){if(sum+i*(k-step)>n)break;dfs(step+1,i,sum+i);}}intmain(){cin>>n>>k;dfs(0,1,0);cout<<ans;return0;}
