数的划分

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 700 字

DFS 强制每份不递减来去重计数

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1440
// 题意：把整数 n 分成 k 个非空部分，不考虑顺序（即 1,1,5 与 1,5,1 算同一种），求不同分法的种数。
// 思路：DFS 枚举，强制每一份不递减，从而天然去重。
// 1. 递归状态为「还要分 dep 份、剩余 rest、下一份不得小于 start」。
// 2. 剪枝：当前份 x 满足 x * dep <= rest，否则后面每份都不小于 x 会超。
// 复杂度：O(划分数) 时间 / O(k) 空间
// 易错点：去重的关键是让每一份不小于前一份，而不是下标递增，否则会重复计数。
// 易错点：递归到 dep = 0 时不仅要判断 rest = 0，还要保证上一份不超过它，否则会漏掉终止条件。
#include <bits/stdc++.h>
using namespace std;
int n, k, ans;
void dfs(int rest, int dep, int start){
    if(dep == 0){
        if(rest == 0) ans++;
        return;
    }
    for(int x = start; x * dep <= rest; x++) dfs(rest - x, dep - 1, x);
}
int main(){
    if(!(cin >> n >> k)) return 0;
    dfs(n, k, 1);
    cout << ans << "\n";
    return 0;
}

数的划分

正文

一本通·提高篇的其它内容