方法一：二分法
先从50
再从25或75……
方法二：平方根法
方法三：解方程法（最优解）
假设这个问题存在最优解，这个最优解的最坏尝试次数是X次。那么我们第一次扔鸡蛋应该考虑哪一层？
那么 如果鸡蛋没有摔碎，我们的尝试次数消耗了一次，而下一次仍鸡蛋的地方就变成了x+x-1层。 因为问题变成了 从100-x层往下扔，要求次数不超过x-1层。
同理： 下一次
需要使用动态规划的思想。
如何找到状态转移方程：
通过上述方程我们知道了X次数与X层的关系。
那么，此方程如何求解？
根据DP规则，我们采用自底向上的方式求解方程，如3个鸡蛋4层楼
而对于两个鸡蛋两层楼：
接下来两个鸡蛋三层楼：
最终得到
这里可以做一些优化 将空间复杂度优化到o（m）
版权声明
1.本站大部分下载资源收集于网络，不保证其完整性以及安全性，请下载后自行测试。
2.本站资源仅供学习和交流使用，版权归资源原作者所有，请在下载后24小时之内自觉删除。
3.若作商业用途，请购买正版，由于未及时购买和付费发生的侵权行为，与本站无关。
4.若内容涉及侵权或违法信息，请联系本站管理员进行下架处理，邮箱ganice520@163.com（本站不支持其他投诉反馈渠道，谢谢合作）
发表评论