高楼扔鸡蛋（LeetCode 887）

题目描述

动态规划和二分搜索（理解什么是最坏情况下的最小次数）

思路和算法

我们可以考虑使用动态规划来做这道题，状态可以表示成，其中 鸡蛋数， 为楼层数。当我们从第 楼扔鸡蛋的时候：

• 如果鸡蛋不碎，那么状态变成 ，即我们鸡蛋的数目不变，但答案只可能在上方的 层楼了。也就是说，我们把原问题缩小成了一个规模为 的子问题；
• 如果鸡蛋碎了，那么状态变成 ，即我们少了一个鸡蛋，但我们知道答案只可能在第 楼下方的 层楼中了。也就是说，我们把原问题缩小成了一个规模为 的子问题。

这样一来，我们定义 为在状态 下最少需要的步数。根据以上分析我们可以列出状态转移方程：

这个状态转移方程是如何得来的呢？对于 而言，我们像上面分析的那样，枚举第一个鸡蛋扔在的楼层数 。由于我们并不知道真正的 值，因此我们必须保证 鸡蛋碎了之后接下来需要的步数 和 鸡蛋没碎之后接下来需要的步数 二者的 最大值 最小，这样就保证了在 最坏情况下（也就是无论 的值如何） 的值最小。如果能理解这一点，也就能理解上面的状态转移方程，即最小化。

难点：本题最难的地方就是“最坏情况下的最小值”。这里给出一些理解：
值是确定的，但它不是题目要我们求的。题目要我们求的是找到这个 值的最小实验次数。这其实是时间复杂度的概念，时间复杂度是在最坏情况下（即运气最差的情况下），程序执行完毕最少执行的次数，例如：

• 在一个数组（长度为 ）里查找一个数，找到某个数可以用线性查找，最好情况下，下标为 的位置就是要找的元素，但是在计算复杂度的时候，需要考虑到最差情况，即看到最后一个位置的时候，才找到这个元素，因此至少执行数组长度这么多次的查找，才能找到；
• 在一个有序数组（长度为 ）里查找，可以使用二分查找算法，最好情况下依然是 次就找到（中点位置），但是最坏情况下，例如中点的两个邻居，就得找 （这个数值需要上取整，这里不深究）次；

题目中的「最小」字眼很让人迷惑，我的理解是：把求解 的过程认为是用最好的算法，即使是在最坏的运气下，为了准确得到结果，找到 这个值的实验的次数最少是多少。正是因为用「最好的算法」，谈「最少次数」才有意义，这一点是比较绕的。

代码

public int dropEgg(int K, int N) {
        int[][] dp = new int[K + 1][N + 1];
        // 初始化
        for (int i = 1; i <= K; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = j;
            }
        }
        for (int i = 2; i <= K; i++) {
            for (int j = 2; j <= N; j++) {
                for (int x = 2; x < j; x++) {
                    dp[i][j] = Math.min(dp[i][j], 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]));
                }
            }
        }
        for (int i = 0; i <= K; i++) {
            System.out.println();
            for (int j = 0; j <= N; j++) {
                System.out.print(dp[i][j] + " ");
            }
        }
        return dp[K][N];
    }