题解 | #[NOIP2001]数的划分#

#include <iostream>
 
using namespace std;
const int N = 205;
int n, k, ans;
 
//k:当前还需要拆分的份数
//P:上一份拆分的数字
//n:当前剩余待拆分的整数数值
void dfs(int k, int p, int n) //（初始状态：需要分 3 份，上一份的值为 0，剩余 7 要分配）
{
    if(k == 1) 
    {
        ans++;
        return;
    }
     
    for(int i = 1; i <= n / k; i++) 
    {
        if(i >= p)//避免重复，比如前面拆出较小的数，后面拆的数不小于前面的 
        {
            dfs(k - 1, i, n - i);
        }
    }
}
 
int main() 
{
    cin >> n >> k;
    dfs(k, 0, n);
    cout << ans ;  
    return 0;
}
//第一层递归（k=3;p=0;n=7）

//循环 i 从 1 到 n/k=7/3=2（即 i=1,2）
//条件 i >= p（p=0，所以 1 和 2 都满足）
//当 i=1 时：
//    递归调用 dfs(k=2, p=1, n=7-1=6);
//    进入第二层递归分支A
//当 i=2 时：
//    递归调用 dfs(k=2, p=2, n=7-2=5)
//    进入第二层递归分支B



//第二层递归

//分支 A：dfs(k=2, p=1, n=6)
//    循环 i 从 1 到 n/k=6/2=3（即 i=1,2,3）
//    条件 i >= p（p=1，所以 1、2、3 都满足）
//    A1：i=1 时：
//        递归调用 dfs(k=1, p=1, n=6-1=5)
//        满足 k==1，ans 加 1（ans=1，对应分法 1+1+5）
//    A2：i=2 时：
//        递归调用 dfs(k=1, p=2, n=6-2=4)
//        满足 k==1，ans 加 1（ans=2，对应分法 1+2+4）
//    A3：i=3 时：
//        递归调用 dfs(k=1, p=3, n=6-3=3)
//        满足 k==1，ans 加 1（ans=3，对应分法 1+3+3）

//分支 B：dfs(k=2, p=2, n=5)
//    循环 i 从 1 到 n/k=5/2=2（即 i=1,2）
//    条件 i >= p（p=2，只有 i=2 满足）
//    B1：i=2 时：
//        递归调用 dfs(k=1, p=2, n=5-2=3)
//        满足 k==1，ans 加 1（ans=4，对应分法 2+2+3）