高楼扔鸡蛋解题思路

1. 带「备忘录」的递归算法

• 把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。
• 造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。
  一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。

常规解题思路

• 找到这个问题有什么「状态」，有什么「选择」，然后穷举。
  「状态」很明显，就是当前拥有的鸡蛋数 K 和需要测试的楼层数 N。
  「选择」其实就是去选择哪层楼扔鸡蛋。
  现在明确了「状态」和「选择」，动态规划的基本思路就形成了：肯定是个二维的 dp 数组或者带有两个状态参数的 dp 函数来表示状态转移；外加一个 for 循环来遍历所有选择，择最优的选择更新状态：

      private int getCount(int egg, int floor) {
        int res = 0;
        for (int i = 1; i <= floor; i++) {
            res = Math.min(res, 这次在第 i 层楼扔鸡蛋);
        }
        return res;
    }

这段伪码还没有展示递归和状态转移，不过大致的算法框架已经完成了。

• 找到状态转移方程
  我们选择在第 i 层楼扔了鸡蛋之后，可能出现两种情况：鸡蛋碎了，鸡蛋没碎。注意，这时候状态转移就来了：
  如果鸡蛋碎了，那么鸡蛋的个数 K 应该减一，搜索的楼层区间应该从 [1..N] 变为 [1..i-1] 共 i-1 层楼；
  如果鸡蛋没碎，那么鸡蛋的个数 K 不变，搜索的楼层区间应该从 [1..N] 变为 [i+1..N] 共 N-i 层楼。
• 写出递归代码
  因为我们要求的是最坏情况下扔鸡蛋的次数，所以鸡蛋在第 i 层楼碎没碎，取决于哪种情况的结果更大：

    private int getCount(int egg, int floor) {
        int res = 0;
        for (int i = 1; i <= floor; i++) {
            res = Math.min(res, Math.max(
                    getCount(egg - 1, i - 1)// 碎了
                    , getCount(egg, floor - i) + 1)//没碎
                    + 1  // 在第 i 楼扔了一次
            );
        }
        return res;
    }

• ** 找到递归的 base case**
  当楼层数 N 等于 0 时，显然不需要扔鸡蛋；当鸡蛋数 K 为 1 时，显然只能线性扫描所有楼层：

  if (egg <= 1) return floor;
  if (floor <= 0) return 0;

• 添加一个备忘录消除重叠子问题

 public static int getCount(int egg, int floor, HashMap<String, Integer> dict) {
        String key = egg + "_" + floor;
        int res = 0;
        if (egg <= 1) return floor;
        if (floor <= 0) return 0;
        //备忘录,避免重复计算
        if (dict.containsKey(key)) {
            return dict.get(key);
        }
        // 用二分搜索代替线性搜索
        int lo = 1, hi = floor;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int broken = getCount(egg - 1, mid - 1, dict);
            int notBroken = getCount(egg, floor - mid, dict);
            if (broken > notBroken) {
                hi = mid - 1;
                res = Math.min(res, broken + 1) + 1;
            } else {
                lo = mid + 1;
                res = Math.min(res, notBroken + 1) + 1;
            }
        }
        dict.put(key, res);
        return res;
    }

这个算法的时间复杂度是多少呢？动态规划算法的时间复杂度就是子问题个数 × 函数本身的复杂度。
函数本身的复杂度就是忽略递归部分的复杂度，这里 getCount 函数中有一个 for 循环，所以函数本身的复杂度是 O(N)。
子问题个数也就是不同状态组合的总数，显然是两个状态的乘积，也就是 O(KN)。
所以算法的总时间复杂度是 O(K*N^2), 空间复杂度 O(KN)。

疑难解答

这个问题很复杂，但是算法代码却十分简洁，这就是动态规划的特性，穷举加备忘录/DP table 优化，真的没啥新意。

首先，有读者可能不理解代码中为什么用一个 for 循环遍历楼层 [1..N]，也许会把这个逻辑和之前探讨的线性扫描混为一谈。其实不是的，这只是在做一次「选择」。

比方说你有 2 个鸡蛋，面对 10 层楼，你这次选择去哪一层楼扔呢？不知道，那就把这 10 层楼全试一遍。至于下次怎么选择不用你操心，有正确的状态转移，递归会算出每个选择的代价，我们取最优的那个就是最优解。

另外，这个问题还有更好的解法，比如修改代码中的 for 循环为二分搜索，可以将时间复杂度降为 O(KNlogN)；再改进动态规划解法可以进一步降为 O(KN)；使用数学方法解决，时间复杂度达到最优 O(K*logN)，空间复杂度达到 O(1)。

二分的解法也有点误导性，你很可能以为它跟我们之前讨论的二分思路扔鸡蛋有关系，实际上没有半毛钱关系。能用二分搜索是因为状态转移方程的函数图像具有单调性，可以快速找到最值。

简单介绍一下二分查找的优化吧，其实只是在优化这段代码：

res = Math.min(res, Math.max(
                  getCount(egg - 1, i - 1)// 碎了
                  , getCount(egg, floor - i) + 1)//没碎
                  + 1  // 在第 i 楼扔了一次
          );

首先我们根据getCount(egg, floor) 数组的定义（有 egg面对floor 层楼，最少需要扔几次），很容易知道 egg 固定时，这个函数一定是单调递增的，无论你策略多聪明，楼层增加测试次数一定要增加。

那么注意 getCount(egg - 1, i - 1) 和 getCount(egg, floor - i) 这两个函数，其中 i 是从 1 到 floor 单增的，如果我们固定 egg 和floor把这两个函数看做关于 i 的函数，前者随着 i 的增加应该也是单调递增的，而后者随着 i 的增加应该是单调递减的：

这时候求二者的较大值，再求这些最大值之中的最小值，其实就是求这个交点嘛，熟悉二分搜索的同学肯定敏感地想到了，这不就是相当于求 Valley（山谷）值嘛，可以用二分查找来快速寻找这个点的。

进阶版解题思路

• 重新定义状态转移
  基础版本是确定当前的鸡蛋个数和面对的楼层数，就知道最小扔鸡蛋次数。最终我们想要的答案就是 dp(K, N) 的结果。
  现在，我们稍微修改 定义，确定当前的鸡蛋个数和最多允许的扔鸡蛋次数，就知道能够确定 F 的最高楼层数。具体来说是这个意思：

dp[k][m] = n
当前有 k 个鸡蛋，可以尝试扔 m 次鸡蛋
这个状态下，最坏情况下最多能确切测试一栋 n 层的楼

比如说 dp[1][7] = 7 表示：
现在有 1 个鸡蛋，允许你扔 7 次;
这个状态下最多给你 7 层楼，
使得你可以确定楼层 F 使得鸡蛋恰好摔不碎
（一层一层线性探查嘛）

这其实就是我们原始思路的一个「反向」版本，我们先不管这种思路的状态转移怎么写，先来思考一下这种定义之下，最终想求的答案是什么？

我们最终要求的其实是扔鸡蛋次数 m，但是这时候 m 在状态之中而不是 dp 数组的结果，可以这样处理：

int superEggDrop(int K, int N) {

  int m = 0;
  while (dp[K][m] < N) {
      m++;
      // 状态转移...
  }
  return m;
}

题目不是给你 K 鸡蛋，N 层楼，让你求最坏情况下最少的测试次数 m 吗？while 循环结束的条件是 dp[K][m] == N，也就是给你 K 个鸡蛋，测试 m 次，最坏情况下最多能测试 N 层楼。
但是现在这种 dp 定义根本不需要这些了，基于下面两个事实：

1、无论你在哪层楼扔鸡蛋，鸡蛋只可能摔碎或者没摔碎，碎了的话就测楼下，没碎的话就测楼上。

2、无论你上楼还是下楼，总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）。

根据这个特点，可以写出下面的状态转移方程：

dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1

dp[k][m - 1] 就是楼上的楼层数，因为鸡蛋个数 k 不变，也就是鸡蛋没碎，扔鸡蛋次数 m 减一；

dp[k - 1][m - 1] 就是楼下的楼层数，因为鸡蛋个数 k 减一，也就是鸡蛋碎了，同时扔鸡蛋次数 m 减一。

PS：这个 m 为什么要减一而不是加一？之前定义得很清楚，这个 m 是一个允许的次数上界，而不是扔了几次。

至此，整个思路就完成了，只要把状态转移方程填进框架即可：

int superEggDrop(int K, int N) {
  // m 最多不会超过 N 次（线性扫描）
  int[][] dp = new int[K + 1][N + 1];
  // base case:
  // dp[0][..] = 0
  // dp[..][0] = 0
  // Java 默认初始化数组都为 0
  int m = 0;
  while (dp[K][m] < N) {
      m++;
      for (int k = 1; k <= K; k++)
          dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
  }
  return m;
}

如果你还觉得这段代码有点难以理解，其实它就等同于这样写：

for (int m = 1; dp[K][m] < N; m++)
  for (int k = 1; k <= K; k++)
      dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;

看到这种代码形式就熟悉多了吧，因为我们要求的不是 dp 数组里的值，而是某个符合条件的索引 m，所以用 while 循环来找到这个 m 而已。

这个算法的时间复杂度是多少？很明显就是两个嵌套循环的复杂度 O(KN)。

另外注意到 dp[m][k] 转移只和左边和左上的两个状态有关，所以很容易优化成一维 dp 数组，这里就不写了。

参考资料

基础
进阶