nyoj 90 整数划分

点击打开链接

整数 划分

时间限制：3000 ms | 内存限制：65535 KB
难度：3

描述
将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，

其中n1≥n2≥…≥nk≥1，k≥1。

正整数n的这种表示称为正整数n的划分。求正整数n的不

同划分个数。

例如正整数6有如下11种不同的划分：

6；

5+1；

4+2，4+1+1；

3+3，3+2+1，3+1+1+1；

2+2+2，2+2+1+1，2+1+1+1+1；

1+1+1+1+1+1。

输入
第一行是测试数据的数目M（1<=M<=10）。以下每行均包含一个整数n（1<=n<=10）。

输出
输出每组测试数据有多少种分法。

样例输入

1

6

样例输出

经典动态规划问题,状态描述的方式有很多,我也只是知道其中一种,假设dp( x, y)表示数x最大能分成 y 个数,我们可以想象成 x 个球放在 y 个格子里,那么拆分时有两种情况,第一种是每个盒子里都至少有一个球,那么先把每个格子里放一个球,这样就剩下了x - y个球,那么把剩下的( x - y)个球放在y个盒子里,这就转移到了dp( ( x - y), y)这个状态; 另一种情况就是至少有一个盒子里没有球,这样就把状态转移成了dp( x, y - 1)这个状态;所以最后dp( x, y) = dp(x
- y, y) + dp(x, y - 1),这就是转移方程,但是需要注意一个细节,就是如果x - y < y,也就是说当第一种情况下剩下的球的个数小于盒子的总个数,那么dp的值就不存在了,比如把5分成至少6个数,这样本身就不合理,所以这种情况下我们就要比较一下,对于x - y < y的,我们要把方程中的y换成x - y,因为x - y 个球最大就能分成x - y个数

#include<stdio.h>

int main()

{

	int map[11][11] = {0};

	int i , j , k ;

	map[0][0] = 1;

	for(i = 1 ; i < 11 ; i++)

	{

		for(j = 1 ; j <= i ; j++)

		{

			if(j > i - j)

				map[i][j] = map[i][j - 1] + map[i - j][i - j];

			else

				map[i][j] = map[i][j - 1] + map[i - j][j];

		}

	}

	scanf("%d" , &i);

	while(i--)

	{

		scanf("%d" , & j);

		printf("%d\n" , map[j][j]);

	}

	return 0;

}