[数据结构与算法]动态规划——1304：数的划分

1304：数的划分

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 4500 通过数: 2763
【题目描述】
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5； 1，5，1； 5，1，1；

问有多少种不同的分法。 输出一个整数，即不同的分法。

【输入】
两个整数n，k(6<n≤200，2≤k≤6)，中间用单个空格隔开。

【输出】
一个整数，即不同的分法。

【输入样例】
7 3
【输出样例】
4
【提示】
四种分法为：1，1，5；1，2，4；1，3，3；2，2，3。

分析
不能空只要在能为空的基础上先每个盆子都分配一个即可
能为空设为dp[n][k]
不能为空则为dp[n-k][k]

#include<bits/stdc++.h>
#define N 210
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;

int n,k,dp[N][N];
int main(){
	cin>>n>>k;
	memset(dp,0,sizeof(dp));
	for(int i=0;i<=n-k;i++){
		for(int j=0;j<=k;j++){
			if(i<=1 || j<=1) dp[i][j]=1;
			else if(i<j) dp[i][j]=dp[i][i];
			else dp[i][j]=dp[i-j][j]+dp[i][j-1]; 
		}
	}
	cout<<dp[n-k][k];
	return 0;
}