链接：https://ac.nowcoder.com/acm/problem/16695
来源：牛客网
将整数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<iostream> 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; }
原文：https://www.cnblogs.com/ALINGMAOMAO/p/10313354.html