【题目来源】https://www.luogu.com.cn/problem/P1025【题目描述】将整数 n 分成 k 份且每份不能为空任意两个方案不相同不考虑顺序。例如n7k3下面三种分法被认为是相同的。1,1,51,5,15,1,1。问有多少种不同的分法。【输入格式】n, k6n≤200, 2≤k≤6。【输出格式】1 个整数即不同的分法。【输入样例】7 3【输出样例】4【数据范围】6n≤200, 2≤k≤6【算法分析】● 剪枝策略能够大幅减少搜索范围避免无意义的深度遍历与回溯压缩时间开销显著优化 DFS 枚举、组合排列、路径规划等问题的运行效率是深度优先搜索中提升算法性能的关键优化手段。● 代码关键要素解析// cur当前已经分好的份数// sum当前分出来的数的总和// pre下一份允许选取的最小值保证非递减避免重复方案// 剪枝1if(sumn) return;→ 当前总和已经超过 n直接返回。// 剪枝2int ipre;→ 保证非递减从 pre 开始避免重复方案。// 剪枝3i*(k-cur)sumn→ 剩下份数全取 i 也不会超 n否则剪枝。// dfs(0,0,1); → 初始状态已分 0 份总和 0下一份允许选取的最小值为 1。【算法代码】#include bits/stdc.h using namespace std; int n,k,ans; void dfs(int cur,int sum,int pre) { if(sumn) return; //Pruning 1 if(curk) { if(sumn) ans; return; } //Pruning 2~3 for(int ipre; i*(k-cur)sumn; i) { dfs(cur1,sumi,i); } } int main() { cinnk; dfs(0,0,1); coutansendl; return 0; } /* in:7 3 out:4 */【参考文献】https://www.luogu.com.cn/problem/solution/P1025