編程算法 - 劃分數 代碼(C)

編程算法 - 劃分數 代碼(C)

劃分數 代碼(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