扔鸡蛋问题(四种解法)
转载自:程序员小灰
方法一:二分法
先从50
再从25或75……
方法二:平方根法
方法三:解方程法(最优解)
假设这个问题存在最优解,这个最优解的最坏尝试次数是X次。那么我们第一次扔鸡蛋应该考虑哪一层?
那么 如果鸡蛋没有摔碎,我们的尝试次数消耗了一次,而下一次仍鸡蛋的地方就变成了x+x-1层。 因为问题变成了 从100-x层往下扔,要求次数不超过x-1层。
同理: 下一次
需要使用动态规划的思想。
如何找到状态转移方程:
通过上述方程我们知道了X次数与X层的关系。
那么,此方程如何求解?
根据DP规则,我们采用自底向上的方式求解方程,如3个鸡蛋4层楼
而对于两个鸡蛋两层楼:
接下来两个鸡蛋三层楼:
最终得到
这里可以做一些优化 将空间复杂度优化到o(m)
优化代码如下: