数的划分

题目描述
将整数 分成 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：，下面三种分法被认为是相同的：

1,1,5; 1,5,1; 1,1,5.

问有多少种不同的分法。

输入格式
两个整数， 和 。

输出格式
输出不同的分法数。

样例
输入样例
7 3
输出样例
4
样例说明
四种分法为：1,1,5; 1,2,4; 1,3,3; 2,2,3.

数据范围与提示
对于 100% 的数据6≤n≤200，2≤k≤6。

解题思路

设f(i,j)为i分成j份的方案数
初值：
当j=1以及i=j时f(i,j)=1
递推：
两种情况

1.j份中至少一个是1，方案数为f(i-1,j-1)
2.j份中一份1都没有，考虑将i-j分为j份，再往j份中的每一份+1，方案数为f(i-j,j）

故有递推式：
f ( i , j ) = f ( i − 1 , j − 1 ) + f ( i − j , j ) f(i,j)=f(i-1,j-1)+f(i-j,j) f(i,j)=f(i−1,j−1)+f(i−j,j)

AC代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,f[205][10];
int main()
{
   
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=min(i,k);j++)
	  if(j==1||i==j)f[i][j]=1;//初值
	  else f[i][j]=f[i-j][j]+f[i-1][j-1];//递归
	printf("%d",f[n][k]);  
 	return 0;
}

谢谢