程序设计实验题5.3 瓜分车厘子

程序设计语言综合设计实验题5.3 瓜分车厘子

★实验任务

大家一定小时候都做过很多奇奇怪怪的分水果的题目，比如7个小朋友分3个苹果，切4刀怎么分比较合理。

然而我们今天要分的是车厘子，自然不可能把车厘子切开来分。事实上，负责分配车厘子的Gyy也很随意，他只要能把给定的n个车厘子分成k份就可以了，根本不在乎谁多谁少，请帮忙Gyy算一下，一共会有多少种分配方案。请注意，每份不能为空，如果一种分法能够通过调换顺序变成另一种，那么认为他们是相同的，比如：

1,1,8；8,1,1；1,8,1；这三种分法视为同一种方案。

★输入格式

输入共一行，给出两个整数n,k，其中6<n≤200，2≤k≤6。

★输出格式

输出共一行，即不同的分法的方案数。

★输入样例

7 3

★输出样例

4

★Hint

四种分法为：1,1,5; 1,2,4; 1,3,3; 2,2,3。

思路：本题的数据范围很小，直接用搜索就能AC，时间复杂度O（n^k）。
但如果数据范围稍微增大一些，显然搜索就会超时！
因此可以用一种巧妙的dp做法解决此问题。
状态表示：dp[i][j]表示将i个车厘子分成j个的方法数。
状态转移：咕咕咕。
代码：

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

int dp[200][10];

int main(){
	int n,k;
	cin>>n>>k;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=i; j++){
			if (j==1 || j==i) dp[i][j]=1;
			else dp[i][j]=dp[i-1][j-1]+dp[i-j][j];
		}
	printf("%d",dp[n][k]);
	return 0;
}