P1025 [NOIP2001 提高组] 数的划分

题目传送门

题目描述

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

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

1,1,5；
1,5,1；
5,1,1；

问有多少种不同的分法。

输入格式

n,k （6<n≤200，2≤k≤6）

输出格式

1 个整数，即不同的分法。

输入输出样例

输入 

7 3

输出

4

对于提高-来说，这题太**水了！明明有类似的普及-啊！蒟蒻都会！

//有可以优化算法的地方请巨佬们及时指出！！！（QAQ）

#include<bits/stdc++.h>
using namespace std;
int n,k,f[201][7];
int main()
{
    cin >> n >> k;
    for (int i=1;i<=n;i++)
	{
	f[i][1]=1;
	f[i][0]=1;
	}
	for (int p=2;p<=k;p++) 
	{
	f[1][p]=0;
	f[0][p]=0;
	} 
    for (int i=2;i<=n;i++)
        for (int p=2;p<=k;p++)
            if (i>p) f[i][p]=f[i-1][p-1]+f[i-p][p];
            else f[i][p]=f[i-1][p-1];
    cout<<f[n][k];
    return 0;
}

小递归~