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

[labuladong]

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

评论礼仪 见这里，违者直接拉黑。

[sonymoon]

递归+备忘录 lc上超时了

[1302304703]

备忘录+递归确实会超时 在第74个用例的时候,输入数据是: s = 6 , n = 10000

class Solution {
    int[][] memo;

    public int superEggDrop(int k, int n) {
        memo = new int[k + 1][n + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -999);
        }
        return dp(k, n);
    }

    //k个鸡蛋,n层楼,返回最优结果
    public int dp(int k, int n) {
        //base case
        if (k == 1) {
            return n;
        }
        if (n == 0) {
            return 0;
        }

        //备忘录
        if (memo[k][n] != -999) {
            return memo[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);
        }

        memo[k][n] = res;
        return res;
    }
}

[cheng-miao]

1

[Maxiah]

会超时，但是想往之前的套路里塞一塞

class Solution {
public:
    vector<vector<int>> memo;   // 备忘录
    int superEggDrop(int k, int n) {
        // 自底向上的DP

        // 状态：鸡蛋，楼层
        // 选择：碎没碎
        memo = vector<vector<int>>(k+1, vector<int>(n+1));

        // dp[i][j]表示：当前手握i个鸡蛋身处j层楼的最少扔鸡蛋次数是dp[k][j]。
        vector<vector<int>> dp(k+1, vector<int>(n+1));

        // base case
        for(int i = 1; i < dp.size(); i++){
            for(int j = 1; j < dp[0].size(); j++){
                dp[i][j] = j;
            }
        }
        

        // 穷举所有状态
        // int res = INT_MAX;
        for(int i = 2; i < dp.size(); i++){ // 鸡蛋
            for(int j = 1; j < dp[0].size(); j++){  // 楼层
                // 穷举选择：在第几层楼扔
                // 碎了，去楼下
                // 没碎，去楼上

                for(int h = 1; h <= j; h++){
                    dp[i][j] = min(dp[i][j],
                                   max(dp[i - 1][h - 1], dp[i][j-h]) + 1);
                }
            }
        }

        return dp[k][n];
    }
};