高楼扔鸡蛋问题

887.鸡蛋掉落

// 当前状态为 (K 个鸡蛋，N 层楼)
// 返回这个状态下的最优结果
int dp(K, N):
    int res
    for 1 <= i <= N:
        res = min(res, 这次在第 i 层楼扔鸡蛋)
    return res
    
base case:
    if K == 1: return N
    if N == 0: return 0

如果鸡蛋碎了，那么鸡蛋的个数K应该减一，搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼

如果鸡蛋没碎，那么鸡蛋的个数K不变，搜索的楼层区间应该从 [1..N]变为[i+1..N]共N-i层楼

最坏情况下扔鸡蛋的次数，所以鸡蛋在第i层楼碎没碎，取决于哪种情况的结果更大

🔽🔽🔽

Map<String, Integer> map = new HashMap<>();
int dp(int K, int N) {
        int res = Integer.MAX_VALUE;
        if (K == 1) return N;
        if (N == 0) return 0;
        if (map.containsKey(K + "*" + N)) {
            return map.get(K + "*" + N);
        }
        for (int i = 1; i < N + 1; i++) {
            // 最坏情况下的最少扔鸡蛋次数
            res = Math.min(res,
                    //最坏情况下
                    Math.max(dp(K, N - i), // 没碎
                            dp(K - 1, i - 1)) //碎
                            + 1 //在第 i 楼扔了一次
            );
        }
        map.put(K + "*" + N, res);
        return res;
    }

结果超时了，可以将for循环改成二分搜索

Map<String, Integer> map = new HashMap<>();
public int dp2(int K, int N) {
        if (!map.containsKey(K+"*"+N)) {
            int ans;
            if (N == 0)
                ans = 0;
            else if (K == 1)
                ans = N;
            else {
                int lo = 1, hi = N;
                while (lo + 1 < hi) {
                    int x = (lo + hi) / 2;
                    int t1 = dp(K - 1, x - 1);
                    int t2 = dp(K, N - x);

                    if (t1 < t2)
                        lo = x;
                    else if (t1 > t2)
                        hi = x;
                    else
                        lo = hi = x;
                }

                ans = 1 + Math.min(Math.max(dp(K - 1, lo - 1), dp(K, N - lo)),
                        Math.max(dp(K - 1, hi - 1), dp(K, N - hi)));
            }

            map.put(K+"*"+N, ans);
        }

        return map.get(K+"*"+N);
    }