划分数 代码(C)
?
?
?
题目: 有n个无区别的物品, 将它们划分成不超过m组, 求出划分方法数模M的余数.
例如: n=4的m=3个划分, result=4(1,1,2; 1,3; 2,2; 4)
?
使用动态规划(DP)方法,
n的m划分a, 如果每个i都有a, {a-1}的集合就是n-m的m划分; a=0时, 就是n的m-1划分.
递推公式: dp[i][j] = dp[i][j-i] + dp[i-1][j]
?
代码:
?
/*
* main.cpp
*
* Created on: 2014.7.20
* Author: spike
*/
/*eclipse cdt, gcc 4.8.1*/
#include
#include
class Program { static const int MAX_N = 100; int n=4, m=3; int M=10000; int dp[MAX_N+1][MAX_N+1]; public: void solve() { dp[0][0] = 1; for (int i=1; i<=m; ++i) { for (int j=0; j<=n; ++j) { if (j-i>=0) { dp[i][j]=(dp[i-1][j]+dp[i][j-i])%M; } else { dp[i][j]=dp[i-1][j]; } } } printf(result = %d , dp[m][n]); } }; int main(void) { Program iP; iP.solve(); return 0; }
输出:
?
?
result = 4
?
?
?
?
?