鸡蛋掉落--一步一步的dp

0x01.问题

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

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

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

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

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

1 <= K <= 100 1 <= N <= 10000

输入示例：
K = 1, N = 2
输出示例：
2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

谷歌经典面试题

public int superEggDrop(int K, int N)

0x02.一步一步的dp分析

初读题目，读不懂，没关系，再读一遍，发现题目的要点：

• 需要从一栋楼中找到刚好会使鸡蛋破碎的楼层。
• 鸡蛋数量是指定的。
• 每次移动可以取一个鸡蛋。
• 最终需要求的并不是F，而是找到F的最少次数。

前面的暂时都很好理解，看到最后一个有点懵，找到F的最少次数怎么去求呢？

题目还有一个条件，那就是无论F的初始值是多少。

将这些条件加在一起，暂时没有头绪，无从下手。我们看一下题目的输入输出示例，发现这个去寻找F的过程是这样子的：

• 尝试一层，如果鸡蛋没碎，说明需要找的F还在更上层，反之，就在下面的层数里。

我们单单就这个寻找的小问题来说，如果需要求解最少的次数，是不是应该这样：

• 先看上面的层数寻找的次数和下面的层数寻找的次数哪个大，因为前提条件是无论F初始值是多少，说明要考虑上下最差的情况，然后再取这个最差的情况里面的最小值，就是我们最终所需要求的。

我们仔细的分析一下这个问题需要用什么方法去求解：

• 我们可以发现，每一个问题，都能分割成很多子问题，于是可以采用动态规划的思想去做。
• 在寻找得过程中，由于是按楼层去搜索的，而楼层是有序的，所有可以使用二分查找去搜索。

确定了动态规划后，开始寻找状态：

• 对这个问题影响的只有K和N，所以状态肯定是K,N。
• 我们假设dp[i][j]表示一共有 i 层楼梯的情况下，使用 j 个鸡蛋的最少实验的次数。

第二步，寻找状态转移方程：

• 根据上面的分析，在尝试了某一层后，dp[i][j]应该等于上下次数最大值中的最小值。
• dp[i][j]=min{max(dp[k-1][j-1],dp[i-k][j]+1)} (1<=k<=i)

第三步，初始化条件：

• 当楼层为0时，dp[0][j]=0
• 当楼层为1时，dp[1][j]=1
• 有特例，dp[1][0]=0
• 当鸡蛋为0时，dp[i][0]=0
• 其它情况，初始化dp[i]为一个最大值i。

0x03.解决代码–dp+二分

class Solution {
    public int superEggDrop(int K, int N) {
        int dp[][]=new int[N+1][K+1];
        //初始化第0层和第1层的情况
        for(int j=0;j<=K;j++){
            dp[0][j]=0;
            dp[1][j]=1;
        }
        dp[1][0]=0;
        for(int i=2;i<=N;i++){
        	//初始化dp[i]为最大值i
            Arrays.fill(dp[i],i);
            dp[i][0]=0;
        }
        for(int i=2;i<=N;i++){
            for(int j=2;j<=K;j++){
                int left = 1;
                int right=i;
               //二分法
                while(left<right){
                    int mid = left + (right - left + 1) / 2;
                    if(dp[mid-1][j-1]>dp[i-mid][j]){
                        right=mid-1;
                    }else{
                        left=mid;
                    }
                }
                dp[i][j]=Math.max(dp[left-1][j-1],dp[i-left][j])+1;
            }
        }
        return dp[N][K];
    }
}

• 时间复杂度：O(K*N*logN)
• 空间复杂度：O(K*N)

心情日记：哪有什么一夜成名，都是百炼成钢！

ATFWUS --Writing By 2020–04-11