链接：

来源：牛客网

将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。

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

1，1，5; 1，5，1; 5，1，1;

问有多少种不同的分法。

输入：n，k ( 6 < n ≤ 200，2 ≤ k ≤ 6 )

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

 

 

思路都是相同的：都是分为两种情况，

　　　　　　　　1：减1的情况，这样就会产生一种新的数，

　　　　　　　　2：减去k，这个k是k个数都共同的。

我的思路：就是一般dfs的思路，这样的时间复杂度非常大。因为，每次都需要遍历200，而递归的深度为6，这样时间复杂度非常大，所以是40%的代码过了。

#include
     
      using namespace std;const int N = 210;int dp[N][N];int main(){    for (int i = 0; i <= 200; ++i)        dp[0][i] = 0;    for (int i = 1; i <= 200;++i)    for (int j = 1; j <= 6; ++j){        if (i < j)dp[i][j] = 0;        else if (i == j)dp[i][j] = 1;        else dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];    }    int n, k;    cin >> n >> k;    cout << dp[n][k] << endl;}