鸡蛋掉落问题分析

李恒道

https://leetcode.cn/problems/super-egg-drop/description/

第一步我们其实很容易分析出来递归
首先拥有K个鸡蛋，可能N层楼
第一个鸡蛋可能在任意一层为最优
则遍历1...N
每层都尝试落鸡蛋，取所有的最小操作次数
而落鸡蛋有两种可能，假设楼层在T
一种是蛋碎了，则问题转化为在K-1个蛋在1..T-1层放鸡蛋的问题
一种是蛋没碎，则问题转化为K个蛋在T+1到N层放鸡蛋的问题
很容易得到递推公式
取最大(dp[鸡蛋 - 1][当前楼层 - 1], dp[鸡蛋][最高楼层 - 当前楼层]) + 1

那我们可以很容易写出来dp代码

var superEggDrop = function (k, n) {
    // k蛋数量
    const dp = new Array(k + 1).fill(0).map(() => new Array(n + 1).fill(Number.MAX_SAFE_INTEGER))
    for (let index = 0; index < dp[0].length; index++) {
        dp[1][index] = index
    }
    for (let index = 0; index < dp.length; index++) {
        dp[index][0] = 0;
    }
    for (let index = 2; index < dp.length; index++) {
        for (let indey = 1; indey < dp[0].length; indey++) {
            const layoutHeight = indey;
            for (let currentLayout = 1; currentLayout <= layoutHeight; currentLayout++) {
                dp[index][indey] = Math.min(dp[index][indey], Math.max(dp[index - 1][currentLayout-1], dp[index][layoutHeight - currentLayout])+1)
            }
        }
    }
    return dp.pop().pop()
};

是该代码复杂度为(K*N方)
实际跑下来虽然结果正确会超时，这步我就没思路了
看了labuladong大佬的解
https://leetcode.cn/problems/super-egg-drop/solutions/44427/ji-ben-dong-tai-gui-hua-jie-fa-by-labuladong/

其中可以发现dp[鸡蛋 - 1][当前楼层 - 1]，随着遍历的楼层逐渐增加，结果也会增大
而dp[鸡蛋][最高楼层 - 当前楼层])随着遍历楼层的逐渐增加，最高楼层 - 当前楼层会变得越来越小，结果也会减小
二者之间取最大，则一定存在一个沟壑
可以采用二分法进行获取，复杂度就变成了(KNLogN)
则单纯替换遍历为二分既可以通过

var superEggDrop = function (k, n) {
    // k蛋数量
    const dp = new Array(k + 1).fill(0).map(() => new Array(n + 1).fill(Number.MAX_SAFE_INTEGER))
    for (let index = 0; index < dp[0].length; index++) {
        dp[1][index] = index
    }
    for (let index = 0; index < dp.length; index++) {
        dp[index][0] = 0;
    }
    for (let index = 2; index < dp.length; index++) {
        for (let indey = 1; indey < dp[0].length; indey++) {
            const layoutHeight = indey;
            let l = 0, r = layoutHeight;
            while (l <= r) {
                const center = Math.floor((l + r) / 2);
                let result1 = dp[index - 1][center - 1] ?? Number.MIN_SAFE_INTEGER //随着楼层增高逐渐增大
                let result2 = dp[index][layoutHeight - center] //随着楼层增高逐渐变小
                dp[index][indey] = Math.min(dp[index][indey], Math.max(result1, result2) + 1);
                if (result1 <= result2) {
                    l = center + 1
                } else {
                    r = center - 1
                }
            }
        }
    }
    return dp.pop().pop()
};

这时候如果转换dp思维就可以得到一种更简单的解法
假设有k个蛋，但是只有m次机会，那一共能覆盖多少楼层？
可以分两种情况来进行讨论
假设现在有一个高无限层，低无限层的大楼
有k个蛋，m次机会，此时在某个点砸一颗蛋
那蛋有两种可能，一种碎了，此时向下有多少层可以覆盖到
一种是没有碎，此时向上有多少层可以覆盖到
两种可能相加到一起的总楼层数再加上本层就可以得到k个蛋m次机会能覆盖到多少的楼层
代码直接参考labuladong的就可以了
不是特别复杂就不再写了