经典动态规划：高楼扔鸡蛋（进阶） :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：经典动态规划：高楼扔鸡蛋（进阶）

[deepbreath373]

java:

class Solution {
    Map<String, Integer> memo = new HashMap<>();
    public int superEggDrop(int k, int n) {
        return dp(k, n);
    }
    private int dp(int k, int n){
        if(k == 1){
            return n;
        }
        if(n == 0){
            return 0;
        }
        if(memo.containsKey(k + ":" + n)){
            return memo.get(k+":"+n);
        }
        int res = Integer.MAX_VALUE;
        // for(int i = 1; i <= n; i++){
        //     res = Math.min(res, Math.max(dp(k, n - i), dp(k-1, i-1))+1);
        // }
        int lo = 1, hi = n;
        while(lo <= hi){
            int mid = lo + (hi - lo) / 2;
            int broken = dp(k-1, mid-1);
            int not_broken = dp(k, n-mid);
            if(broken > not_broken){
                hi = mid - 1;
                res = Math.min(res, broken + 1);
            }else{
                lo = mid + 1;
                res = Math.min(res, not_broken + 1);
            }
        }
        memo.put(k+":"+n,res);
        return memo.get(k+":"+n);
    }
}

[sonymoon]

dp[k][m - 1] 就是楼上的楼层数，因为鸡蛋个数 k 不变，也就是鸡蛋没碎，扔鸡蛋次数 m 减一；

博主，有点没看懂，根据dp定义，第二维是楼层数的话，这里为啥不是dp[k][N-m]

[z-ak-z]

@sonymoon m是指”允许扔的最大次数“，扔过一次之后，就变成了”m-1“次。 ”dp[k][m - 1]“ 是指，k个鸡蛋、最多扔m-1次，能够测量出来多少的楼层N。