从小到大地划分

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define MOD 998244353
using namespace std;
int n,k,ans;
//x记录上一个选的数，并且要求这次选的数要不小于上次选的数
void dfs(int x,int now,int sum)
{
//	cout<<x<<" "<<now<<" "<<sum<<endl;
	if(now==k)
	{
		if(sum<=n-x)
		{
			ans++;
//			cout<<ans<<endl;
		}
		return;
	}
	for(int i=x;sum+i<=n;i++)
		dfs(i,now+1,sum+i);
//	book[x][k-now]=0;
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	dfs(1,1,0);
	cout<<ans<<endl;
	return 0;
}

dfs

#include <bits/stdc++.h>
using namespace std;
int n, k;
int ans;
// 考虑第 now 份怎么分
// 最少分 minN 个，之前所有数之和为 sum
void dfs(int now, int minN, int sum)
{
    if (now > k)
    {
        if (sum == n)
            ans++;
        return;
    }
    //之前的和为 sum
    //now 后面的 (k-now) 个数都至少是 minN
    for (int i = minN; i <= n - sum - (k - now) * minN; i++)
        dfs(now + 1, i, sum + i);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    ans = 0;
    dfs(1, 1, 0);
    cout << ans << "\n";
    return 0;
}

dp

• dp[i][j]: i 分成 j 组非 0 的方案数
• dp[i-1][j-1]: i 分成 j 份，至少存在一组大小为 1 的方案数
• dp[i-j][j]: i 分成 j 份，不存在大小为 1 的组方案数（先每个位置都铺一个 1，然后再要求分成 j 份，不允许为空）

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

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    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++)
            if (i >= j)
                dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
    cout << dp[n][k] << endl;
    return 0;
}