题目描述

这日，快码佳编四兄弟姐妹来到了一个山脚下，只听一个老奶奶给两个孙子讲故事。
你听说过三只小猪的故事吗？这是一个经典的故事。很久很久以前，有三只小猪。第一只小猪用稻草建的房子，第二个小猪用木棍建的房子，第三个小猪则使用砖做为材料。一只大灰狼想吃掉它们并吹倒了稻草和木棍建的房子。但是砖盖的房子很结实，狼最终也没有破坏掉，最后小猪们战胜了大灰狼并把它尾巴烧掉了。
为了自己的安全，小猪们又建造了一个新砖房。但是现在问题出现了，怎样把三个小猪分配到两个房子里呢？第三只小猪是三只小猪中最聪明的一只，为了不浪费任何一个房子，它总共考虑了三种方案，如下图

但是将来怎么办呢？”第三只小猪知道将来随着成员的增多，它们将会盖更多的房子。它想知道给定了房子和猪的数目后，房子的分配方案有多少，但这个问题对于它来说，很明显有点难了，你能帮小猪解决这个问题吗？

输入

多组测试数据，每组一行，包含两个整数n和m，分别表示小猪的数目和房间数（1≤n≤20，0≤m≤20）。

 

输出

每组输出一行，仅一个整数，表示将n只小猪安置在m个房间且没有房间空闲的方案数。

 

很明显这是一个递归的问题，问题就是如何找到递归的公式，

先考虑几种简单的情况：

第一种是没有房子（即m=0），那么分配方案数为0；//ways[][0]=0

第二种是猪的数量n小于房子的数量m（显然即使一个房子一头猪也填不满），所以分配方案也为0；//ways[n][m]=0

第三种是猪的的数量n等于房子的数量m（不考虑不同房子的区别0），所以分配方案为1种（即一个房子一头猪）。//ways[n][m]=1

下面只考虑一般情况，也就是猪的的数量n大于房子的数量m（n>m）时ways[n][m]。

当n==3，m==2时，我们可以很容易得出三种情况

当猪的数量加1时，房子数没变时求ways[4][2]，可以这样理解：

这只猪只有两种住法：

1.和别的猪一起住：那么应该可以得出这样的住法总共为：ways[3][2]*2   //乘以2是因为每种分配方案有两间房可以供挑选（方案a中，猪p4，可以和p1 p2他两住在一起，也可以是和p3住在一起）

2.自己一个房间：那么应该可以得出这样的住法总共为：ways[3][1](剩下的三头猪住一间房)。

 

 

注：为撒不考虑房子增加的情况

我们可以假设房子数固定，一只猪一只猪地加，当猪的数量小于房子数量均为0，等于时均为1。

那么加房子时，只要房子数等于猪的数量均为1，大于猪的数量均为0，其余的情况way[n][m]就可以理解为猪数量的叠加。

(ways[3][1]=ways[2][1]*1+ways[2][0]均满足)

 

给出最后的公式ways[n][m]=way[n-1][m]*m+ways[n-1][m-1].

 

代码如下：

#include <stdio.h>
void w(long long ways[][25]){
	int i,j;
	for (i=1;i<=20;i++){
		for (j=0;j<=20;j++){
			if (j==0)ways[i][j]=0;
			else if (j>i)ways[i][j]=0;
			else if (j==i)ways[i][j]=1;
			else if (i>j)ways[i][j]=ways[i-1][j]*j+ways[i-1][j-1];
		}
	}
}
int main()
{
	int n,m;
	while (scanf("%d%d",&n,&m)!=EOF){
	long long ways[25][25];
	w(ways);
	printf("%lld\n",ways[n][m]);
	}
	
	return 0;
}

 

如有不妥，留言评论，轻喷！！！