分割数 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 有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 <stdio.h>

#include <memory.h>

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\n", dp[m][n]);

	}

};

int main(void)

{

	Program iP;

	iP.solve();

	return 0;

}

输出:

result = 4