NYOJ 279 队花的烦恼二和NYOJ 176 整数划分(二)【dp问题或递归】

原题链接：点击。。279 点击。。 176

这两个题 意思基本一样的，就是测试数据的范围不一样。。176数据比较水的，一般不会超时的，但279 你用递归可能就会超时了。。简单讲一下用dp做题的思路吧 。

首先 定义f ( i , j )为整数 i 分成 j 个整数 的情况。。。

经过分析可得f（i， j ）可转化为两个部分：

一： 假设 分成的 j 个整数中 不包含1。。那么 此时 f （ｉ－ｊ，ｊ）就是这部分的总情况。。明白吗？再说清楚一点吧。。既然想让他不包含１，就先将ｊ个整数都分为１，此时ｉ变为ｉ－ｊ，再将ｉ分为ｊ个整数，这ｊ个整数再加上原先分的１，就肯定不会再有１出现了。。ｏｋ了吧。。

二：　假设分成的ｊ个整数至少有一个１。。那么此时ｆ（ｉ－１，ｊ－１）就是这部分的总情况了。。这点都明白了吧。不明白自己分析一下吧。。

结论：ｆ（ｉ，ｊ）＝ｆ（ｉ－ｊ，ｊ）＋ｆ（ｉ－１，ｊ－１）；动态转移方程有了，实现起来不困难吧。。对了，初始化还有些小技巧。。自己琢磨吧。。还有就是用题上数据范围不是很大得，所以暴力求解会很快的。。

２７９代码：

 
#include<stdio.h>
int main()
{
	int a,b,n,m,k;
	int ok[505][7]={0};
	ok[1][1]=1;
	for(a=2;a<=500;a++)
	{
		for(b=1;b<=a&&b<=6;b++)
			ok[a][b]=ok[a-b][b]+ok[a-1][b-1];
	}
	while(~scanf("%d%d",&n,&m))
	{	
		printf("%d\n",ok[n][m]);
	}
}        

１７６代码：

 
#include<stdio.h>
int main()
{
	int a,b,n,m,k;
	int ok[105][105]={0};
	ok[1][1]=1;
	for(a=2;a<=100;a++)
	{
		for(b=1;b<=a;b++)
			ok[a][b]=ok[a-b][b]+ok[a-1][b-1];
	}
	scanf("%d",&k);
	while(k--)
	{
		scanf("%d%d",&n,&m);
		printf("%d\n",ok[n][m]);
	}
}