連接：https://www.luogu.com.cn/problem/P1025

?

?

題目描述

將整數(shù)nn分成kk份，且每份不能為空，任意兩個方案不相同(不考慮順序)。

例如：n=7n=7，k=3k=3，下面三種分法被認為是相同的。

1,1,51,1,5;
1,5,11,5,1;
5,1,15,1,1.

問有多少種不同的分法。

輸入格式

n,kn,k?(6<n \le 2006<n≤200，2 \le k \le 62≤k≤6)

輸出格式

11個整數(shù)，即不同的分法。

輸入輸出樣例

輸入 #1復(fù)制

7 3

輸出 #1復(fù)制

4

說明/提示

四種分法為：
1,1,5
1,2,4
1,3,3
2,2,3

【題目來源】

NOIP 2001 提高組第二題

?

觀看了大佬的博客寫的題解，頗有感謝，借用一下例子。

?

一開始真的對這道題沒思路，也沒有什么想法，然而看了這位大佬的例子，恍然大悟。

?

先寫出狀態(tài)轉(zhuǎn)移方程：dp[i][j]=dp[i-j][j]+dp[i-1][j-1];

?

i表示整數(shù)為i，j表示分成j份。那么對于把i這個數(shù)分成j份的分發(fā)，有兩種情況。

要么就是已經(jīng)將i-1分成了j-1份，只要再分多一個1就可以了。即dp[i-1][j-1]

要么就是在把i-j已經(jīng)分成了j份，只要每一份都+1，就成了把i分成j份的情況了。即dp[i-j][j]

?

然后就是考慮初始化的問題了。

我們考慮，哪些情況可以是已經(jīng)知道方案數(shù)的，最明顯的就是方案數(shù)為1的情況。

方案數(shù)為1的情況有哪些呢？

把i分成0份，分成1份，或者分成k份時，都是只有1種情況。

所以將這幾種狀態(tài)初始化為1即可。

代碼：

#include<iostream>
using namespace std;
int n,k;
long long 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]=dp[i][0]=1;
	for(int i=2;i<=n;i++)
	  for(int j=2;j<=k;j++)
	  {
			if(i>j)
			  dp[i][j]=dp[i-j][j]+dp[i-1][j-1];
			else
			  dp[i][j]=dp[i-1][j-1];
	  }
	cout<<dp[n][k];  
	
	return 0;
}

?