题目阅读和理解

题目出处来自Leecode：887. 鸡蛋掉落

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

[DP、二分查找优化、改数组定义优化]高楼扔鸡蛋 - 图1

你的目标是确切地知道 F 的值是多少。即给定你能够尝试的鸡蛋数、以及给你高度的楼层，我需要知道那个为了得到这个扔下去就碎的“F”楼层，我需要 最少移动多少步？

识别和分析

问题有两个变化量，鸡蛋数量k和楼层n，可以构成一个状态(k,n)，让我们求这个状态对应的一个移动最小值。

定义dp数组/函数

首先确定我们的问题可能是使用一个二维数组dp[i][j]来实现转态的存储和转移或者是 一个dp(k,n)的二参函数。

这里如果是使用dp函数来实现转态转移，我们定义dp函数为dp(int k,int n)，表示：当k个鸡蛋，在n层楼上，找摔碎楼层的最小移动数（或者说扔鸡蛋的次数，因为移动一楼摔一个鸡蛋嘛）。

状态转移

确定完dp函数的含义，现在要来研究，当处于状态k,n的时候，我的状态是如何转移的？

当我们在第i层的时候，我们遇到的 可能 有两种：

  1. 一种是鸡蛋碎掉
  2. 一种是鸡蛋没碎

作为一个正常人，如果鸡蛋碎掉，按照正常人的想法，我再去拿一个鸡蛋，然后去下一楼试试，因为如果下一楼如果摔不碎鸡蛋的话，那么i层就是题目中所谓的“F层”

如果鸡蛋没碎，那么还是原来那个鸡蛋，我要去挑战更高的楼层。接下去我就要去往上面去搜寻题目中所谓的“F层”。

在上面两端的叙述中，k和n是怎么变化的？

  1. k在鸡蛋碎掉的情况下，因为k要重新拿一个，根据k的定义，这种情况要求k-1。
  2. k在鸡蛋没碎的情况下，还是原来鸡蛋，鸡蛋数k没变

那么n是怎么变化的？

注意，这个n并不是表示某一层楼，比如健身房在5楼。而是表示面对的楼层数量，比如摩天大楼有100个楼层，农村小平房有3个楼层。这是我们面对的楼层数

当我们确定1i去除了 如图，接下去我们的搜寻范围就是绿色块。。

[DP、二分查找优化、改数组定义优化]高楼扔鸡蛋 - 图2

怎么知道“找到F了”

这道题比较不好想的是，如何表示我找到F了，其实我个人觉得这是这题里面比较隐晦的东西，参考书上说的也不是很清楚。其实弄清楚这个问题，就是在确定BaseCase，和二维数组不同，二维数组一般需要确定dp[0][0]之类的数值，但是对于递归函数来说，我们需要一个“触底反弹”的return语句，当我们遇到这个情况的时候，我们想要的答案，能够不断的从递归栈里面给我们弹出来。

当我们找到所谓的F层的时候，我们的状态是怎么样的？

我们的楼层数肯定是没有了，因为我们把这个楼层搜索的区间（如上面所述）都压缩到了0，这个为0的搜寻范围，其实就不是所谓的范围了，你就处于这栋大楼刚好能摔碎的楼层里。

但是还有一种情况，非常糟糕，也就是说，当你的鸡蛋数为1的时候，这个时候你要面对的范围有多大你就要去搜寻多大，因为题目要得知的是你在这个状态的“最坏情况下”扔掉鸡蛋的次数。

给你一个鸡蛋和100层楼，告诉我，你觉得你最坏情况要扔几次鸡蛋/爬几层楼？

当然是100层啊，这个时候，你只需要return 这个楼层数就行了，因为你只有一个鸡蛋，最坏情况就是来几层爬几层。return n;即可。

综上总结一下，本题的baseCase就是如下两个

  1. 楼没了，找到了！从return 0开始不断向上递交答案。
  2. 蛋快没了，只剩下一个了！最坏情况我已经知道了，从return n开始不断向上递交答案。

基本思路

到此为止，状态和转移都大概的摸清楚了之后，代码大概的思路是什么？

首先我们要拟定一个dp函数，我们要确定框架和里面的基本要素

  1. int dp(int k,int n){
  2.         //...bc的处理？
  3.       int res = = Integer.MAX_VALUE;;
  4.     for (int i = 1; i <=n; i++) {
  5.         res = Math.min(res,...);
  6.     }
  7.     return res;
  8. }

问你最少的移动次数，一定是要对每一个状态的所有选择里面选取最小的，Math.min(res,...) 的选择就是无脑写上去。

我们都知道，在每一个状态（鸡蛋数k和面对楼层n）都会有1~n层楼的尝试，每一次尝试都会有两种状态（碎了和没碎）。

  • 从1~n个尝试里面，我要选取最小的答案，因为你从1楼开始扔、从50楼开始扔、从100楼开始扔得到的结果是不一样的。并且你很难知道，给你100层楼，和5个鸡蛋，他具体的人鸡蛋的楼层尝试路径是什么样的，比如扔完100楼去扔37楼完事儿之后去X楼。你只知道某种选择存在，并且得到的扔鸡蛋数是最少的。
  • 但是对于每一个状态转移出去的两个状态（碎了、没碎）我又需要知道他们里面最坏情况，也就是对于状态k,n来说，经过一系列的碎、不碎、碎、不碎…的很多种情况的比较，我们能得到一个最坏的、得到扔鸡蛋次数最多的那一种“碎-不碎”组合。这个组合使我们在这个kn状态下可能遇到的最坏情况了。
  • 对于dp(k,n)来说，通过比较dp(k-1,i-1)和dp(k,n-i)得到的答案都是知道的，我既然知道子问题的答案，对于我这层的答案来说，无非就是为了结果多扔一次罢了。

所以我们可以更加确定，我们的方程状态转移方程为

dp(K, N) = \min_{0 <= i <= N}{\max{dp(K - 1, i - 1), dp(K, N - i)} + 1}

代码实现

根据之前的想法和思考，我们继续完善之前的代码。

  1. int dp(int k,int n){
  2.     if (k==1){//只有一个鸡蛋了，最坏情况就是有几层试几层
  3.         return n;
  4.     }
  5.     if (n==0){//需要搜索的楼层没了，说明找到了！
  6.         return 0;
  7.     }
  8.     int res = = Integer.MAX_VALUE;;
  9.     for (int i = 1; i <=n; i++) {//面对n层楼，我有1~n个起始楼层选择
  10.         res = Math.min(res,Math.max(dp(k-1,i-1),dp(k,n-i))+1);//为了结果多扔一次
  11.     }
  12.     return res;
  13. }

起始这个时候我们应该要意识到，这个递归产生的树是非常庞大的，我们需要使用一个备忘录去保存结果，实现以下剪枝来优化时间复杂度。最后产生的代码是这样的

  1. int superEggDrop(int k,int n){
  2.     Map<String, Integer> memo = new HashMap<>();
  3.     return dp(k,n,memo);
  4. }
  6. /**
  7.  *
  8.  * @param k k个鸡蛋
  9.  * @param n n层楼
  10.  * @return
  11.  */
  12. int dp(int k,int n,Map<String, Integer> memo){
  13.     if (k==1){
  14.         return n;
  15.     }
  16.     if (n==0){
  17.         return 0;
  18.     }
  19.     //创建key(字符串做的二元组)和检查memo是否预存此答案
  20.     String key = k+""+n;
  21.     if (memo.containsKey(key)){
  22.         return memo.get(key);
  23.     }
  24.     //res是一个不断减小的过程
  25.     int res = Integer.MAX_VALUE;
  26.     for (int i = 1; i <=n; i++) {
  27.         res = Math.min(res,
  28.                 Math.max(dp(k-1,i-1,memo),dp(k,n-i,memo))
  29.                         +1);
  30.     }
  31.     //保存和更新memo
  32.     memo.put(key,res);
  34.     return res;
  35. }

但是很不幸，超时了，说明这题在时间复杂度上依旧没有满足要求，我们还可以继续优化这个算法

优化1：二分查找优化思路

优化思路

提供了一个二分搜索优化的思路，在之前，我们是设想 从1~n个楼层，我们每一个楼层都要去试一下，让后选择最少次数的最坏情况扔鸡蛋数。 for (int i = 1; i <=n; i++)

现在拿出dp(k,n)函数来讨论，当鸡蛋数量固定的时候，dp(k,n)随着n越大，函数值也越大。这个结论很容易想出来，因为你面对的楼层越多，你尝试的次数就要越多。

明确了上面这个特性来看dp(k,n-i)（没碎）和dp(k-1,i-1)碎了，把k和n这两个给定的量固定住，i这个变量是递增的。

  • dp(k,n-i)很明显是递减的，因为i递增，n-i递减。
  • dp(k-1,i-1)很明显是递增的。

根据状态转移方程。

dp(K, N) = \min_{0 <= i <= N}({\max{dp(K - 1, i - 1), dp(K, N - i)} + 1})

对于 $\max{dp(K - 1, i - 1), dp(K, N - i)}$，相当于是求两个函数的较大部分，可以草图如下，注意红色部分才是函数的部分图像。

[DP、二分查找优化、改数组定义优化]高楼扔鸡蛋 - 图3

而上面最小值，即橙色的那个点，我们就正好对应函数里面的min函数来对其进行求取。

所以我们想要找到的点，就是在两个函数的交点，类似与一个山谷的最低点一样。而两个函数交点的特征，就是 dp(K - 1, i - 1)== dp(K, N - i)

代码实现

那么上面这种利用二分查找的算法如何去简化查找这个点的过程呢？代码如下：

  1. int res = Integer.MAX_VALUE;
  3. int lo=1,hi = n;
  4. while (lo<=hi){
  5.     int mid = (lo+hi)/2;
  6.     int broken = dp(k-1,mid-1,memo);
  7.     int notBroken = dp(k,n-mid,memo);
  9.     if (broken>notBroken){
  10.         hi = mid-1;
  11.         res = Math.min(res,broken+1);
  12.     }else {
  13.         lo = mid+1;
  14.         res = Math.min(res,notBroken+1);
  15.     }

上面代码解释如下：

  • 设置二分查找的low指针和high指针，while循环退出的时候，即low>high的时候，即找到了这个要求的点
  • 在while循环内，检查其碎和没碎的两种情况的扔鸡蛋数量
    • 若碎的结果较大，说明点在mid左边
    • 若没碎的结果较大，说明点在mid右边
  • 不管点在mid的左边还是右边，每一次处理都需要
    • 改变low和high的相对位置，在下次的迭代里面再次计算mid。hi = mid-1;或者lo = mid+1;
    • 更新最小的结果值。res = Math.min(res,notBroken或者broken+1);
  • 当循环结束的时候，low>high，我们总能找到这个两个函数相交的点。

优化2：改变DP数组/函数的定义

优化思路

之前的dp函数的定义是什么？当k个鸡蛋，在n层楼上，找确定所谓”F楼“最小的扔鸡蛋次数m。

与之相等的dp数组的定义其实也很容易迁移过来：dp[k][n] = m，k个鸡蛋，n层高的楼，值为m次最小的扔鸡蛋次数。

那么现在改一下dp数组的含义：dp[k][ m] =n，给k个鸡蛋，最多m次的扔鸡蛋次数，求最多的能处理范围为n层高的楼。

这个思路其实是之前的dp数组的定义的逆向版本。现在如何找这个状态转移方程？

现在我们处于一个状态dp[k][ m]，我们扔下去的鸡蛋还是有两个选择

  1. 碎了，鸡蛋少一个，测试次数也减去一次，要想知道这种情况的答案是多少，我们要去单元dp[k-1][ m-1]去获得这个最多能处理的层高的答案。
  2. 没碎，鸡蛋没少，测试次数还是减去一次，要想知道这种情况的答案是多少，我们要去单元dp[k][ m-1]去获得这个最多能处理的层高的答案。

[DP、二分查找优化、改数组定义优化]高楼扔鸡蛋 - 图4

而dp[k][ m]=n是什么意思，最多能处理范围为n层高的楼，你这个n是两个结果的答案的加和！因为你dp[k][ m]=n既有可能是dp[k][ m-1]这个状态多给了一次测试机会，也有可能是来自于dp[k-1][ m-1]这个状态多给了一个鸡蛋和一个测试机会得到的。

换一个理解方式，dp[k][ m]的时候两个状态分别要对应上楼去测和下楼去测，对于上楼去测，我们所知道的能处理的层高的楼其实是知道的，因为根据数学归纳法的思想，子问题的答案我们是已知的。对于下楼去测，我们也知道能处理的层高，而当前dp[k][ m]能处理的楼的层高，就是这两个层高的楼的加和。

所以我们的状态转移公式如下：

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

+1是因为当前层也要算进去！

得到这个式子，我们其实就可以开始编写代码了

代码实现

把上一份代码的函数签名改为int dp(int k,int n)，去掉memo的备忘录

  1. int dp(int k,int n){
  2.     //创建int[k+1][n+1]
  3.     // 即使我们dp数组定义的是dp[k][m]，实际上m必定会在n里面
  4.     int[][] dp = new int[k+1][n+1];
  5.     int m = 0;
  6.     //BC隐含的就是当0，0时候，测试次数为0
  7.     //当指定的鸡蛋数和测试数>给定的楼层的时候，返回当前的m测试次数（下标）
  8.     while(dp[k][m]<n){
  9.         m++;
  10.         //从鸡蛋一个到k个开始
  11.         for (int i = 1; i <=k; i++) {
  12.             dp[i][m] = dp[i-1][m-1]+dp[i][m-1]+1; 
  13.         }
  14.     }
  15.     return m;
  16. }

注意虽然函数的状态转移是如下的形状

[DP、二分查找优化、改数组定义优化]高楼扔鸡蛋 - 图5

这里也不能盲目的套两层循环去做，因为这里定义的是dp[k][m]，m是我们要求的值，和往常的dp[k][m] = n要求的是n不同。这里我们要求的是下标m，而不是n。

所以我们要小心的设置dp数组的大小以及dp数组的遍历方式。

首先： int[][] dp = new int[k+1][n+1];在这里含义其实还是dp[k][ m] =n，给k个鸡蛋，最多m次的扔鸡蛋次数，求最多的能处理范围为n层高的楼。只不过这个m是不可能大于n的，因为你测试的次数再多不可能多于楼层数，所以虽然数组有 [k+1][n+1]这么大，其实表达的含义还是[k][ m]

齐次：既然不能盲目的套两层for循环去做，那么这里遍历的退出条件是什么？

再次回到问题，我们不能忘记初心：当k个鸡蛋，在n层楼上，找确定所谓”F楼“最小的扔鸡蛋次数m在这里，m是一个递增变量，其实当一个最小的鸡蛋k和测试次数m，一旦满足dp[k][m]>n了，就说明我们通过这个最小的m得到了一个n，那么转换过来，题目要求的最小的m我们就已经通过下标体现出来了。所以这里的代码体现就是

  1. while(dp[k][m]<n){
  2.     m++;
  3.     //从鸡蛋一个到k个开始
  4.     for (int i = 1; i <=k; i++) {
  5.         dp[i][m] = dp[i-1][m-1]+dp[i][m-1]+1; 
  6.     }

写完代码，拿一个测试用例（2,6）答案为3 体会一下这个算法的遍历顺序：

[DP、二分查找优化、改数组定义优化]高楼扔鸡蛋 - 图6

小结

从这题可以感受到如下的几点：

  1. 首先这题读懂题目就已经很不容易了，所以对题目的分析能力一定要加强。
  2. 数学归纳法的思维很重要，要反复提醒自己：子问题的最值我们是已知的，对于这个答案，我们可以做些什么
  3. 从 题目变量的识别[DP、二分查找优化、改数组定义优化]高楼扔鸡蛋 - 图7状态的确定[DP、二分查找优化、改数组定义优化]高楼扔鸡蛋 - 图8状态的转移，要有清晰的推理过程
  4. 有时候题目不管给出一个什么场景 摔碗、摔鸡蛋、4个按键…. 我们要关注的还是状态、状态转移等一些DP问题的基本要素，至于这些场景是怎么实现的，我们不需要过度关注和思考，只要关注这个问题的终结状态（比如扔鸡蛋问题的鸡蛋破损，对于k和n是什么情况）在变量上的体现是什么。
  5. 要时时刻刻不忘自己要解决什么问题，数组和函数的定义是什么？
  6. 从优化1的例子得出，在具有单调性的dp函数里面，可以利用二分查找需要元素有序排列的性质，使用二分查找的思想，加快对目标状态的查找。
  7. 从优化2的例子得出，我们的思维可以跳脱一点，当一个问题比较复杂的时候，我们可以尝试改变dp数组的定义，逆向的求解问题。