[887] 鸡蛋掉落

动态规划

details

自顶向下递归

var superEggDrop = function (k, n) {
    let map = new Map();
    return dfs(k, n);

    function dfs(k, n) {
        if (k === 1) return n;
        if (n === 0) return 0;

        const key = `${k}-${n}`;
        if (map.has(key)) return map.get(key);
        let res = Infinity;
        for (let i = 1; i <= n; i++) {
            res = Math.min(res, Math.max(dfs(k - 1, i - 1), dfs(k, n - i)) + 1);
        }
        map.set(key, res);
        return res;
    }
};

二份查找优化

var superEggDrop = function (k, n) {
    let map = new Map();
    return dfs(k, n);

    function dfs(k, n) {
        if (k === 1) return n;
        if (n === 0) return 0;

        const key = `${k}-${n}`;
        if (map.has(key)) return map.get(key);
        let res = Infinity;
        let l = 1,
            r = n;
        while (l <= r) {
            let mid = Math.floor((l + r) / 2);
            let eggBreak = dfs(k - 1, mid - 1); // 鸡蛋碎了，探索下半部分
            let eggNotBreak = dfs(k, n - mid); // 鸡蛋没碎，探索上半部分

            res = Math.min(res, Math.max(eggBreak, eggNotBreak) + 1);

            if (eggBreak > eggNotBreak) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        map.set(key, res);
        return res;
    }
};

自底向上迭代

var superEggDrop = function (k, n) {
    let dp = Array(k + 1)
        .fill(null)
        .map(() => Array(n + 1).fill(Infinity));

    // 初始化边界条件
    for (let i = 0; i <= k; i++) dp[i][0] = 0; // 0 层楼不用实验
    for (let j = 1; j <= n; j++) dp[1][j] = j; // 1 个鸡蛋只能线性试

    // 填充 dp 表格
    for (let i = 2; i <= k; i++) {
        for (let j = 1; j <= n; j++) {
            for (let x = 1; x <= j; x++) {
                dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][x - 1], dp[i][j - x]) + 1);
            }
        }
    }

    return dp[k][n];
};