[LeetCode]Super Egg Drop

这道题也是DP的问题，如果我们用dp[i][j]表示用i个鸡蛋来试j层楼梯的话，我们可以有递推方程：

• dp[i][j] = min(max(dp[i - 1][x], dp[i][j - x]) + 1), where 0 < x <= j

也就说我们遍历这所有j层阶梯，每一次都有对应鸡蛋破和不破的两种情况：

• dp[i - 1][x]对应鸡蛋破了，我们少了一个鸡蛋，但我们定位了答案在前x个阶梯里
• dp[i][j - x]对应鸡蛋没破，鸡蛋数目不变，并且定位了答案在后j - x个阶梯里

我们每次找这两种情况中最坏的，然后整体遍历每一个阶梯之后我们取最小的。很明显的区间PD，假设我们有K个鸡蛋，N个阶梯，时间复杂度为O(K * N^2)，空间复杂度O(K * N)。代码如下：

但这个算法时间复杂度还是太高，没有办法过所有的test case。所以我们仍然需要尝试优化。一个可能的优化是用dp方程的单调性，我们可以注意到dp[i - 1][x]是随着x递增的, 而dp[i][j - x]是随着x递减的，那么根据这个性质，我们可以用binary search找max(dp[i - 1][x], dp[i][j - x])的最小值，具体做法是：

• 对于当前mid，如果dp[i - 1][mid] < dp[i][j - mid]，那么我们可以去[lo, mid]里继续找
• 如果dp[i - 1][mid] > dp[i][j - mid]，那么我们可以去[mid, hi]里继续找
• 如果dp[i - 1][mid] = dp[i][j - mid]，我们就找到了最优点

这样的话时间复杂度可以优化成O(K * N * log N)，代码如下：

bottom up
top down

空间也可以用rolling array来优化到O(N)，代码如下：

这道题我们还可以进一步优化，这次我们不考虑x，转而考虑j。dp[i - 1][x]对于j来讲是常量，然而dp[i][j - mid]是关于j递增的。那么这样的话，最优点也是根据j递增的。比如j = 4的最优点的x肯定是大于等于j = 3的情况的。因为K最多也就是从1增加到N，我们就可以找最优点这一步优化到amortized O(1)的时间。总的时间复杂度就变为O(N * K)，代码如下：