鹰蛋

假设有m层楼，n个鹰蛋，最高从哪层楼扔下时蛋不会碎？f(m, n)为m层楼，n个鹰蛋所需次数。在第i层试探时：1、鹰蛋摔破，下一步只有n-1个鹰蛋，总楼层数缩减为i-1；2、鹰蛋没有摔破，那么鹰蛋总数不变，还是n个，楼层数则缩减为m-i层。递归在以下3个状态结束：1）如果鹰蛋只剩1个，对所有的楼层进行穷举；2）如果楼层是0，则需要试探0次； 3）如果楼层是1，则需要只需要试探1次。

要保证能测出蛋恰好会碎的楼层, 并使此策略在最坏情况下所扔次数最少

动态规划的状态转移：F(m,n)= MIN{ MAX{ F(i-1, n-1) + 1, F(m-i, n)+1}} (0 < i < m)

递归的过程中会重复的解，通过array[M][N]来保存子问题的结果

const int nfloor = 100;
const int negg = 2;
 
#define MAX(a, b) (a) > (b) ? (a) : (b)
 
int arr[nfloor][negg];
 
int test_egg(int nfloors, int neggs)
{	
	if(neggs <= 1)
		return nfloors;
 
	if(nfloors == 0)
		return 0;
 
	if(nfloors == 1)
		return 1;
 
	int min = nfloor;
 
	if(arr[nfloors-1][neggs-1] != 0)
		return arr[nfloors-1][neggs-1];
 
	for(int i = 1; i < nfloors; i++)
	{
		int a = test_egg(i-1, neggs-1) + 1;	
		int b = test_egg(nfloors - i, neggs) + 1;
		int v = MAX(a, b); //有两种情况，要求最坏情况下的所需次数
 
		if(min >  v)
			min = v;//记录所有扔法中次数最少的
	}
 
	arr[nfloors-1][neggs-1] = min;
 
	return min;
 
}
 
int main(int argc, _TCHAR* argv[])
{
 
	memset(arr, 0, nfloor*negg*sizeof(int));
	int a = test_egg(nfloor,negg);
 
	return 0;
}