有趣的题目，思考了一下，应用场景可能包括压力测试这种逐步加量、且有尝试成本的实际问题上。

1884. 鸡蛋掉落-两枚鸡蛋

先考虑1884题，是2枚鸡蛋的情况。
乍一看想不到适合套用的数据结构，考虑是DP的解法。
dp[i][j]，i为当前允许摔碎的鸡蛋数，j为当前需要判定的楼层数，值为操作数。
当i为0时，我们只能逐层判断，所以dp[0][i] = i
当i为1时，我们可以选择在[0, j]范围内的一个楼层k扔鸡蛋，对于每一个k，会存在两种情况：

• 情况1：摔碎了，那么操作数+1，并转化为i-=1，转化为i=0的情况，从底层向上逐层搜索，即dp[0][k-1]+1
• 情况2：没摔碎，那么操作数+1，i不变，再向上，搜索的空间（楼层数）减掉j，即dp[1][j-k]+1
  综合来看，状态转移方程是：

dp[1][j] = min{
        max(dp[0][0]+1, dp[1][j-1]),
        max(dp[0][1]+1, dp[1][j-2]),
        ...
        max(dp[0][k-1]+1, dp[1][j-k]),
        ...
        max(dp[0][j]+1, dp[1][0]),
}

代码写出来长这样：

func twoEggDrop(n int) int {
    const kk = 2
    dp := make([][]int, kk, kk)
    for i:=0;i<kk;i++{
        dp[i] = make([]int, n+1, n+1)
    }
    for i:=0;i<=n;i++{
        dp[0][i] = i
    }

    dp[1][0] = 1
    dp[1][1] = 1
    min := 1000
    sub_max := 0
    for j:=1;j<=n;j++{
        min = 1000
        for k:=1;k<=j;k++{
            sub_max = max(dp[0][k-1]+1, dp[1][j-k]+1)
            if sub_max < min{
                min = sub_max
            }
        }
        dp[1][j] = min
    }

    return dp[1][n-1]
}

func max(i, j int) int{
    if i>j{
        return i
    }else{
        return j
    }
}

887. 鸡蛋掉落

在实际情况中，可能允许我们尝试的次数限制是一个变量。

上面1884题两个鸡蛋的解法，已经将鸡蛋数抽离出来成为变量，可以容易拓展到e个鸡蛋的情况。但是需要注意到，1884的时间复杂度为O(eN^2)。对于e个鸡蛋的情况，效率太低，答题时会出现超时错误。需要寻找优化的方法。

首先观察到上面的式子：

dp[1][j] = min{
        max(dp[0][0]+1, dp[1][j-1]),
        max(dp[0][1]+1, dp[1][j-2]),
        ...
        max(dp[0][k-1]+1, dp[1][j-k]),
        ...
        max(dp[0][j]+1, dp[1][0]),
}

将i=1，j=6带入，可以看看到：

k=0     dp[0][0]=0          dp[1][6-1]=dp[1][5]=3
k=1     dp[0][1]=1      dp[1][6-2]=dp[1][4]=3
k=2     dp[0][2]=2      dp[2][6-3]=dp[1][3]=3
k=3     dp[0][3]=3      dp[3][6-4]=dp[1][2]=2
k=4     dp[0][4]=4      dp[4][6-5]=dp[1][1]=2
k=5     dp[0][5]=5      dp[4][6-6]=dp[1][0]=1
}

可以发现dp[i-1][k-1]与dp[i][j-k]是关于k的两条单调曲线（其实是一条直线和一条分段直线），且存在交点。如图：

交点处的位置也是两条的max合并后的min值，交点对应的值就是dp[i][j]。
这里求交点可以使用二分搜索。

时间复杂度到此被优化到O(eNlogN)，进一步用决策单调性可以优化到O(N)，但是我不会写了Orz。对了，这道题有个彩蛋，把第一题的dp打印出来，可以发现很明显的数学规律，也可以很容易写出一种O(N)时间的神奇解法。

func superEggDrop(e int, n int) int {
    if e == 1 {
        return n
    }

    dp := make([][]int, e+1, e+1)
    for i := 0; i <= e; i++ {
        dp[i] = make([]int, n+1, n+1)
    }

    for i := 1; i <= e; i++ {
        for j := 0; j <= n; j++ {
            dp[i][j] = -1 // -1 视为没有计算过的结果
        }
    }

    return dps(e, n, &dp)
}

// 对dp做二分查找
func dps(i, j int, dp *[][]int) int {
    if (*dp)[i][j] != -1{
        return (*dp)[i][j]
    }
    low := 1 // 0?
    high := j
    var val int
    if j == 0{
        val = 0
    }else if i == 1{
        val = j
    }else{
        k := 0 // mid, sum/2
        for low+1 < high {
            k = (high + low) / 2
            y1 := dps(i-1,k-1,dp)
            y2 := dps(i, j-k, dp)

            if y1<y2{
                low = k
            }else if y1>y2{
                high = k
            }else{
                high, low = k, k
            }
        }
        val = 1+min(max(dps(i-1,high-1,dp), dps(i,j-high,dp)),max(dps(i-1,low-1,dp), dps(i-1,j-low,dp)))
    }
    (*dp)[i][j] = val
    return (*dp)[i][j]
}

func max(i, j int) int {
    if i > j {
        return i
    } else {
        return j
    }
}

func min(i, j int) int{
    if i<j{
        return i
    }else{
        return j
    }
}