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

#include<bits/stdc++.h>
using namespace std;

int n,k;
int ans=0;

void dfs(int x,int y,int z){
    if(z==0&&x==0){
        ans++;
        return;
    }else if(z==0&&x!=0){
        return;
    }
    for(int i=y;i<=x;i++){
        /*
         * 这里的y是已经选择的数，之后再选择的数必须要从这个开始，不能够小于这个数
         * x是还剩下的数，这里犯了个错误，可以等于的，就是那种情况，选择了等于之后，同时z也变为0了，然后就成功了，
        */
        dfs(x-i,i,z-1);
    }
}

int main(){
    scanf("%d%d",&n,&k);//n代表总数，
    /*（输入4 2作为例子）
     * 为什么要设置n呢，为了检查最后选择的是否成立
     * 比如已经分好了 dfs最后分的结果是1 1，
     * 判断是否合理就是拿4去减掉ta们，结果是2，很显然是不对的
     * 如果是分的是1 3,4减掉ta们很显然是可以的，减去之后结果为0
     * 但是你是很难在最后分好之后，用4去减的，除非你将每次选择的数给纪录下来，然后最后再拿4减，很麻烦
     * 每次选好一个之后就减这样分好最后一个数之后，就已经减完了所有的数了，这样是很优雅的
     */
    dfs(n,1,k);
    /*（4 2为例子）
     *三个参数代表还 选择之后剩下的数，已经选择的数，选择之后还需要分成几个数
     * 主函数中的dfs“已经选择的数”为什么是1呢，如果选择是1的话，那么一开始的意思不就是，还剩下4，选择1，还要分2个数。//4 2为例子
     * 不过好像这个一开始的是入口，并不能够算真正开始
     * 进入之后在内部的dfs才是真正的开始，那时三个参数变为3 1 1就合理了
     * 再往下，2 2 0同理。
     * 在dfs犯了个错误，还在思考怎样才可以选第一个数，然后又需要增加什么条件选第二个数
     * 实际上 直接不用管，遍历就是，分好了看看是否合理，合理就可以纪录，不合理继续遍历。
     * 比如这个dfs遍历一开始就是将4分成了两个1和1，最后检验不合理，然后继续。，
    */
    cout<<ans<<endl;
    return 0;
}