这道题有点拗口，就是要知道基本情况：

1 有0楼的时候，就不需要实验了，返回0

2 有1楼的时候，只需要试验一次就可以了

3 有一个蛋的时候，最坏情况就需要把所有楼都试验一次

在这三种基本情况假设下去想这个问题就容易多了

分两个情况：

1 碎蛋：往下走

2 没碎蛋：往上走

无论往上走和往下走都可以截去下面和上面的楼层不考虑

不过注意的就是，碎蛋，那么蛋蛋减小1了，没碎蛋那么蛋蛋不用减小。

理解透彻，那么优化动态规划法就可以写出来了：

下面是GeeksforGeeks的动态规划法和递归法求解，和我写的eggDropDPSaveSpace版本，只使用了2个一维表。只需要记住前一行的信息就能填写下一行的信息，那么就可以只用两个一维表。甚至一个一维表。

递归法很慢，楼层多了就直接算不出来。

/* Function to get minimum number of trails needed in worst
case with n eggs and k floors */
int eggDropDP1(int n, int k)
{
	/* A 2D table where entery eggFloor[i][j] will represent minimum
	number of trials needed for i eggs and j floors. */
	vector<vector<int> > eggFloor(n+1, vector<int>(k+1));
	int res;
	int i, j, x;

	// We need one trial for one floor and0 trials for 0 floors
	for (i = 1; i <= n; i++)
	{
		eggFloor[i][1] = 1;
		eggFloor[i][0] = 0;
	}

	// We always need j trials for one egg and j floors.
	for (j = 1; j <= k; j++)
		eggFloor[1][j] = j; 

	// Fill rest of the entries in table using optimal substructure
	// property
	for (i = 2; i <= n; i++)
	{
		for (j = 2; j <= k; j++)
		{
			eggFloor[i][j] = INT_MAX;
			for (x = 1; x <= j; x++)
			{
				res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
				if (res < eggFloor[i][j])
					eggFloor[i][j] = res;
			}
		}
	}

	// eggFloor[n][k] holds the result
	return eggFloor[n][k];
}

//n eggs and k floors
int eggDropDPSaveSpace(int n, int k)
{
	//特殊处理0或1层楼的时候，和只有一个蛋的时候
	if (k <= 1 || n == 1) return k;
	//i eggs and j floors. 
	vector<vector<int> > eggFloor(2, vector<int>(k+1));
	bool flag = false;

	eggFloor[!flag][1] = 1;
	eggFloor[flag][1] = 1;

	for (int j = 2; j <= k; j++)
		eggFloor[!flag][j] = j;

	for (int i = 2; i <= n; i++)
	{
		for (int j = 2; j <= k; j++)
		{
			eggFloor[flag][j] = INT_MAX;
			for (int x = 1; x <= j; x++)
			{
				int res = 1 + max(eggFloor[!flag][x-1], eggFloor[flag][j-x]);
				if (res < eggFloor[flag][j])
					eggFloor[flag][j] = res;
			}
		}
		flag = !flag;
	}
	return eggFloor[!flag][k];
}

/* Function to get minimum number of trails needed in worst
case with n eggs and k floors */
int eggDrop(int n, int k)
{
	// If there are no floors, then no trials needed. OR if there is
	// one floor, one trial needed.
	if (k == 1 || k == 0)
		return k;

	// We need k trials for one egg and k floors
	if (n == 1)
		return k;

	int min = INT_MAX, x, res;

	// Consider all droppings from 1st floor to kth floor and
	// return the minimum of these values plus 1.
	for (x = 1; x <= k; x++)
	{
		res = max(eggDrop(n-1, x-1), eggDrop(n, k-x));
		if (res < min)
			min = res;
	}

	return min + 1;
}

int main()
{
	int n = 18, k = 136;
	//printf ("\nMinimum number of trials in worst case with %d eggs and "
	//	"%d floors is %d \n", n, k, eggDrop(n, k));
	
	printf ("\nDP1:Minimum number of trials in worst case with %d eggs and "
		"%d floors is %d \n", n, k, eggDropDP1(n, k));

	printf ("\nDP:Minimum number of trials in worst case with %d eggs and "
		"%d floors is %d \n", n, k, eggDropDPSaveSpace(n, k));

	system("pause");
	return 0;
}

Geeks面试题： Egg Dropping Puzzle