鸡蛋题库

鸡蛋掉落

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

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

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中重复使用这枚鸡蛋。

请你计算并返回要确定 f 确切的值的最小操作次数是多少？

方案动态规划

思路: 逆向思维,如果我们可以做 t 次操作，而且有 k 个鸡蛋，那么我们能找到答案的最高的 n 是多少？

状态定义: dp[i][j] 表示可以做i次操作，而且有j个鸡蛋时的最高楼层
状态转移方程:我们需要找出最高的 n，因此我们不必思考到底在哪里扔这个鸡蛋，我们只需要扔出一个鸡蛋，看看到底发生了什么：
- 如果鸡蛋没有碎，那么对应的是dp(i - 1, j)，也就是说在这一层的上方可以有dp(i - 1, j)层
- 如果鸡蛋碎了，那么对应的是dp(i - 1, j - 1)，也就是说在这一层的下方可以有dp(i - 1， j - 1)层
- 可得方程为: dp(i,j)=1+dp(i−1,j−1)+dp(i−1,j)
初始状态: dp[i][j] 初始为0 ，当k≥1 时，dp(1, j)=1
问题答案: 操作次数是一定不会超过楼层数的，当i>=n 时，i 即为所求操作次数

function superEggDrop(k, n) {
    if(n==1){
        return 1
    }
    const dp=new Array(n+1).fill(0).map(value=>new Array(k+1).fill(0));
    for(let i=1;i<=k;i++){
        dp[1][i]=1;
    }
    let result=-1;
    for(let i=2;i<=n;i++){
        for(let j=1;j<=k;j++){
            dp[i][j]=1+dp[i-1][j-1]+dp[i-1][j];
        }
        if(dp[i][k]>=n){
            result=i;
            break;
        }
    }
    return result;
};

性能分析:

时间复杂度：O(knlogn)。我们需要计算 O(kn) 个状态，每个状态计算时需要 O(logn) 的时间进行二分查找。
空间复杂度：O(kn)。我们需要 O(kn) 的空间存储每个状态的解。

鸡蛋掉落​

方案 动态规划​

鸡蛋掉落

方案动态规划