题目传送门

本题共有两种方法，分别是递归深搜和动态规划

方法一：递归深搜

Solution

从小到大一一枚举每一个划分的数，。只要找到一种方案就记录，具体细节代码中有注释。

Code

#include <bits/stdc++.h>
using namespace std;
int n,k,ans;

void dfs(int start,int step,int sum){
    //start表示上一个数，step表示分到了第几个数，
    //sum表示当前已划分数的和 

    if(step==k){
        if(sum==n)ans++;//如果找到一种就记录 
        return ;//剪枝 
    }

    for(int i=start;sum+i*(k-step)<=n;i++)dfs(i,step+1,sum+i);
    //i从start开始枚举，是为了避免重复
    //循环结束条件是为了在枚举过程中要保证后面可以继续划分
}
signed main(){
    cin>>n>>k;

    dfs(1,0,0);

    cout<<ans<<endl;
    return 0;
}

方法二：动态规划

Solution

通过观察可以发现，把n拆分成k个数的方案可以分成两部分：

1. 以1开头的方案

2. 不是以1开头的方案

• 我们发现，以1开头的方案数等于把n-1分成k-1个数的方案数。

为什么呢？

不难发现，所有以1开头的方案除了第一位外，其余数的总和为n-1，个数为k-1，而第一位是固定，因此可以转化为把n-1分成k-1个数的方案数。

• 观察不是以1开头的方案，可以发现方案数等于把n-k分成k个数的方案数。

这又是为什么呢

我们知道，如果把n-k分成k个数，每一位再加上基数1，就能够满足总和n，和不是以1开头两个条件，也就相当于以1开头的方案

由此我们得到了转移方程

$$ dp[i][j]=dp[i-1][j-1]+dp[i-j][j] $$

其中i是指要划分的数，j是指要划分的个数

Code

#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define inf numeric_limits<ll>::max()/2
#define pb push_back
#define sz size
#define fi first
#define se second
#define mkp make_pair
#define pint pair<int,int>
#define pll pair<ll,ll>
#define gcd(a,b) b?gcd(b,a%b):a
#define lcm(a,b) a/(gcd(a,b))*b
#define low_bit(x) x&(-x)
using namespace std;

int n,k;
int dp[210][10];

signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)dp[i][1]=1;//初始化 
    for(int i=1;i<=n;i++){
        for(int j=2;j<=k;j++){//i是指要划分的数，j是指要划分的个数 
            if(i>=j){//只有在i>=j时才能进行数的划分 
                dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
            }
        }
    }
    cout<<dp[n][k]; 
    return 0;
}

//ACplease!!!