1、前言

2、思路

这道题使用动态规划来解决，但是我怎么觉得解决的方式像递归。然后这个代码是超时了的，但是这个比较好理解。

3、代码

class Solution {
    
    private int[][] map;

    public int superEggDrop(int K, int N) {
        map = new int[K + 1][N + 1];
        for(int i = 0; i <= K; i++){
            for(int j = 0; j <= N; j++){
                map[i][j] = -1;
            }
        }
        return dp(K, N);
    }

    private int dp(int K, int N){
        // base case
        // 如果楼层 N 为0，不需要扔鸡蛋，因此 K 为0；
        // 如果鸡蛋 K 为1，则需要线性扫描所有楼层 N
        if(K == 1){
            return N;
        }
        if(N == 0){
            return 0;
        }
        
        if(map[K][N] != -1){
            return map[K][N];
        }

        int res = Integer.MAX_VALUE;
        for(int i = 1; i <= N; i++){
            res = Math.min(res, 
                Math.max(
                    dp(K - 1, i - 1), // 碎了
                    dp(K, N - i) // 没碎
                ) + 1);
        }
        map[K][N] = res;
        return res;
    }
}