package dp.superEggDrop;

/**
 * 887. 鸡蛋掉落
 * 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
 * <p>
 * 已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
 * <p>
 * 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
 * <p>
 * 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：k = 1, n = 2
 * 输出：2
 * 解释：
 * 鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
 * 否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
 * 如果它没碎，那么肯定能得出 f = 2 。
 * 因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。
 * 示例 2：
 * <p>
 * 输入：k = 2, n = 6
 * 输出：3
 * 示例 3：
 * <p>
 * 输入：k = 3, n = 14
 * 输出：4
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= k <= 100
 * 1 <= n <= 104
 */
public class superEggDrop {
    // 考虑每一层扔鸡蛋，扔下去的结果两种，碎、不碎
    // 如果碎了，说明F在0~i-1之间，还需要在1~i-1即i-1层楼中搜索
    // 如果没有碎，说明F在i~N之间，还需要再i+1~N层即N-i层楼中搜索
    // 记dp[i][k]表示有k个鸡蛋，i层楼中确定F的具体值的最小搜索次数
    // 那么，假设某次搜索在第j楼，根据上面的思路，在第j楼扔下，存在两种结果：碎、不碎
    // 然后根据结果分别在j楼上面或者下面的搜索区间继续搜索F的值
    // 因此可以得到递推公式
    // dp[i][k] =min{ max(dp[j-1][k-1], dp[i-j][k]) + 1 | 1<=j<=i  }
    // 显然，k>=1，而i为0时，表示没有任何楼层，那么dp[0][k]=0
    // 当k=1，只有一个鸡蛋，只能线性搜索，dp[i][1]=i
    public static int superEggDrop(int k, int n) {

        int[][] dp = new int[k + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            dp[1][i] = i;
        }

        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                Integer res = Integer.MAX_VALUE;
                for (int l = 1; l <= j; l++) {

                    res = Math.min(res, Math.max(dp[i - 1][l - 1], dp[i][j - l]) + 1);
                }
                dp[i][j] = res;
            }
        }
        return dp[k][n];
    }


    public static void main(String[] args) {
        System.out.println(superEggDrop(2, 6));
    }
}