题目描述
将整数n分成k份，且每份不能为空，问有多少种不同的分法。当n=7,k=3时，下面三种分法被认为是相同的：1,1,5;1,5,1;5,1,1
输入描述:
一行两个数n,k。
输出描述:
一行一个整数，即不同的分法数。
思路：
dp[n][k] 表示 n 分成 k 个非空的数的方案数。
显然 n<k 时 dp[n][k]=0 , n=k 时 dp[n][k]=1;
其他的可以分情况讨论：
1.有1的
2.没1的
第一种情况，方案数为 dp[n-1][k-1]
第二种情况，方案数为 dp[n-k][k] (此时 n 必须大于 k)
so，可以转换为：dp[n][k]=dp[n-1][k-1]+dp[n-k][k]。
dp版AC代码：
#include <iostream> #include <algorithm> using namespace std; int dp[205][10]; int main() { ios::sync_with_stdio; int n, k; cin >> n >> k; dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= min(i, k); j++) { dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j]; } } cout << dp[n][k] << endl; return 0; }
原文：https://www.cnblogs.com/Mashiro-zBlog/p/11480325.html