问题

有一个n层的建筑。如果一个鸡蛋从第k层及以上落下，它会碎掉。如果从低于这一层的任意层落下，都不会碎。

有m个鸡蛋，用最坏的情况下实验次数最少的方法去找到k, 返回最坏情况下所需的实验次数。

样例

给出 m = 2, n = 100 返回 14
给出 m = 2, n = 36 返回 8

概念

在看下面的代码之前，PO主先结合扔鸡蛋这个例子讲下动态规划中的几个概念：

状态转移矩阵：结合下面的例子，直观上看就是一个简单的二维数组，也可以把它叫做“备忘录”，这个备忘录存了上面这个问题的所有子问题的子答案！别小看了这个备忘录，它避免了大量的重复计算。不信，你用2个递归+1个循环实现试试，有2个鸡蛋的情况下，楼层到36就已经慢得快计算不出来结果了！动态规划优势就体现在这儿了！当有很多重复子问题的时候，动态规划就是法拉利，其他暴力枚举递归等等都是QQ大众！

状态：就是备忘录里存的一个个子问题答案，可以简单把理解为：状态=答案

状态转移方程：就是写出母问题和子问题之间的关系！比如扔鸡蛋这个问题，你扔碎了，就转化成了往楼上找的子问题；你扔了没碎，那就转化成了往楼下找的子问题。

步骤

PO主宅心仁厚的把每一个步骤拆开了揉碎了给你们讲，具体细节我都在每一行的代码之上的注释里写的非常详尽。
接下来就是通过一行行代码，配合每行代码上的注释来学习解动态规划的步骤！上车~

利用动态规划JAVA实现扔鸡蛋问题：

public class Solution {
    /*
     * @param eggs: the number of eggs
     * @param floors: the number of floors
     * @return: the number of drops in the worst case
     */
    public int dropEggs2(int eggs, int floors) {
        // write your code here
        //第一步永远是创建动态规划的备忘录,也叫状态转移矩阵
        //记住：二维数组里的length是0-start的，又因为包含层数为0或鸡蛋为0的情况，所以定义行高和列宽的时候自然要加1
        int[][] state = new int[eggs + 1][floors + 1];

        //第二步永远是考虑边界，也就是初始化动态规划的备忘录
        //先考虑eggs的边界
        for (int i=0;i<=floors;i++) {
            //首先是eggs=0的情况
            state[0][i] = 0;
            //然后是eggs=1的情况
            //eggs=1的时候，肯定是从第0层一直往上实验
            state[1][i] = i;
        }
        //再考虑floors的边界
        for (int i=1;i<=eggs;i++) {
            //首先是floors=0的情况
            state[i][0] = 0;
            //然后是floors=1的情况
            state[i][1] = 1;
        }

        //第三步就是状态方程了
        //找递推过程中的两个紧邻步骤之间的关系，如何由子结果得到母结果
        //首先，鸡蛋要从2个开始算，因为0个和1个情况你已经考虑完了
        for (int egg=2;egg<=eggs;egg++) {
            //楼层有多高要从2层起步，因为0层和1层的情况你也考虑完了
            for (int floor=2;floor<=floors;floor++) {
                //看这里！这里就是你还有egg个鸡蛋，一共有floor层的子问题！
                //这里定义一个变量来存储最终结果，找到在哪层扔能达到所扔次数最少的目标，扔鸡蛋次数多了胳膊会酸！
                int result = Integer.MAX_VALUE;
                for (int drop=1;drop<=floor;drop++) {
                    //这里！就是在当前子问题中，你从第drop层扔鸡蛋的情况！
                    //第一种情况，哎呀~碎了！那么剩下的问题就转化成了如何在drop-1层，用egg-1个鸡蛋寻找最优解
                    int broken = state[egg - 1][drop - 1];
                    //第二种请看，卧槽~没碎！问题就转化成了如果再floos-drop层，用egg个鸡蛋寻找最优解
                    int unbroken = state[egg][floor - drop];
                    //两种情况我肯定要取最大值，因为我根本不确定鸡蛋会不会碎，我特么又不是先知！
                    int condition = Math.max(broken, unbroken) + 1;
                    //不断的和上一次的结果做比较，只为得到最优的结果，最少的扔鸡蛋次数！
                    result = Math.min(condition, result);
                }
                //当前子问题（当我有egg个鸡蛋，一共有floor层时）已经for循环完了！撒花~~接下来，就是把结果存到我们的结果矩阵里了！
                state[egg][floor] = result;
            }
        }

        //以上的步骤在不断的往状态矩阵（我把它称作装满结果的大盘子！）填充结果！到这里已经都填充完毕，我们自然就可以取到我们想要的结果啦！
        return state[eggs][floors];
    }
}

如果以上思路对你理解动态规划和扔鸡蛋问题有帮助的话，请支持一下我们的知识易学计划，你捐助的每一分钱都是我们前行的动力，后续会分享更多的干货给大家！

教你彻底理解动态规划——扔鸡蛋问题 Drop Eggs2

教你彻底理解动态规划——扔鸡蛋问题 Drop Eggs2

问题

概念

步骤