LeetCode887. 鸡蛋掉落

LeetCode887. 鸡蛋掉落

开始今天的题目前 我们可以先看李永乐老师关于这个问题的讲解

题目描述

image

方法1 动态规划 + 二分查找

先贴个题解吧,我自己确实还不是很理解透,之后有能力会来填坑

import java.util.Arrays;

public class Solution {

    public int superEggDrop(int K, int N) {
        // dp[i][j]:一共有 i 层楼梯的情况下,使用 j 个鸡蛋的最少仍的次数
        int[][] dp = new int[N + 1][K + 1];
        
        // 初始化
        for (int i = 0; i <= N; i++) {
            Arrays.fill(dp[i], i);
            dp[i][0] = 0;
            dp[i][1] = i;
        }
        for (int j = 0; j <= K; j++) {
            dp[0][j] = 0;
            dp[1][j] = 1;
        }

        dp[1][0] = 0;


        // 开始递推
        for (int i = 2; i <= N; i++) {
            for (int j = 2; j <= K; j++) {
                // 在区间 [1, i] 里确定一个最优值
                int left = 1;
                int right = i;
                while (left < right) {
                    // 找 dp[k - 1][j - 1] <= dp[i - mid][j] 的最大值 k
                    int mid = left + (right - left + 1) / 2;
                    int breakCount = dp[mid - 1][j - 1];
                    int notBreakCount = dp[i - mid][j];
                    if (breakCount > notBreakCount) {
                        // 排除法(减治思想)写对二分见第 35 题,先想什么时候不是解
                        // 严格大于的时候一定不是解,此时 mid 一定不是解
                        // 下一轮搜索区间是 [left, mid - 1]
                        right = mid - 1;
                    } else {
                        // 这个区间一定是上一个区间的反面,即 [mid, right]
                        // 注意这个时候取中间数要上取整,int mid = left + (right - left + 1) / 2;
                        left = mid;
                    }
                }
                // left 这个下标就是最优的 k 值,把它代入转移方程 Math.max(dp[k - 1][j - 1], dp[i - k][j]) + 1) 即可
                dp[i][j] = Math.max(dp[left - 1][j - 1], dp[i - left][j]) + 1;
            }
        }
        return dp[N][K];
    }
}