887. 鸡蛋掉落

困难动态规划逆向 DP（m 次操作、j 个蛋最多能测的楼层数）力扣原题 ↗

题目描述

你有 k 枚完全相同的鸡蛋，以及一栋有 n 层（第 1 层到第 n 层）的楼。

存在一个未知的整数 f（0 <= f <= n）：从高于 f 的楼层扔下的鸡蛋一定会碎，从第 f 层或更低处扔下则不会碎。

每次操作选一枚还没碎的鸡蛋，从某一层 x（1 <= x <= n）扔下。碎了的鸡蛋不能再用，没碎的可以继续使用。

返回在最坏情况下，保证确定 f 的确切值所需的最少操作次数。

示例 1

输入：k = 1, n = 2
输出：2

解释：只有一枚蛋，只能先试 1 楼再试 2 楼，最坏要扔 2 次。

示例 2

输入：k = 2, n = 6
输出：3

示例 3

输入：k = 3, n = 14
输出：4

数据范围

1 <= k <= 100
1 <= n <= 10^4

解题思路：逆向 DP（m 次操作、j 个蛋最多能测的楼层数）

反过来想：给 m 次操作和 j 枚蛋，最多能确定多少层楼？记为 f(m, j)。第一次在某层扔：碎了，用剩下 m-1 次、j-1 枚蛋查下面，最多 f(m-1, j-1) 层；没碎，用 m-1 次、j 枚蛋查上面，最多 f(m-1, j) 层。加上当前层，f(m, j) = f(m-1, j-1) + f(m-1, j) + 1。从 m = 1 开始逐次增加，直到 f(m, k) >= n。用一维数组、j 倒序更新即可。

为什么正确

第 m 次循环结束后，dp[j] = 用 m 次操作、j 枚蛋在最坏情况下能分辨的最多楼层数。

复杂度分析

时间 O(k · m)，其中 m 是答案，不超过 n；空间 O(k)。

易错点

直接用 dp[k][n] = 最少操作次数的定义需要枚举扔蛋楼层，是 O(k n²)，会超时。换成“给定次数能覆盖几层”就不用枚举了。一维更新时 j 必须倒序，因为 dp[j-1] 需要的是上一轮的值。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        dp = [0] * (k + 1)
        m = 0
        while dp[k] < n:
            m += 1
            for j in range(k, 0, -1):
                dp[j] = dp[j - 1] + dp[j] + 1
        return m

class Solution {
    public int superEggDrop(int k, int n) {
        int[] dp = new int[k + 1];
        int m = 0;
        while (dp[k] < n) {
            m++;
            for (int j = k; j >= 1; j--) {
                dp[j] = dp[j - 1] + dp[j] + 1;
            }
        }
        return m;
    }
}

class Solution {
public:
    int superEggDrop(int k, int n) {
        vector<int> dp(k + 1, 0);
        int m = 0;
        while (dp[k] < n) {
            m++;
            for (int j = k; j >= 1; j--) {
                dp[j] = dp[j - 1] + dp[j] + 1;
            }
        }
        return m;
    }
};

func superEggDrop(k int, n int) int {
	dp := make([]int, k+1)
	m := 0
	for dp[k] < n {
		m++
		for j := k; j >= 1; j-- {
			dp[j] = dp[j-1] + dp[j] + 1
		}
	}
	return m
}

var superEggDrop = function(k, n) {
    const dp = new Array(k + 1).fill(0);
    let m = 0;
    while (dp[k] < n) {
        m++;
        for (let j = k; j >= 1; j--) {
            dp[j] = dp[j - 1] + dp[j] + 1;
        }
    }
    return m;
};

function superEggDrop(k: number, n: number): number {
    const dp = new Array(k + 1).fill(0);
    let m = 0;
    while (dp[k] < n) {
        m++;
        for (let j = k; j >= 1; j--) {
            dp[j] = dp[j - 1] + dp[j] + 1;
        }
    }
    return m;
}

载入编辑器，自己跑一遍 →

其他解法

正向 DP 从“给定楼层求次数”出发，需要在转移中找最优楼层；主解法把问题反过来问“给定次数能测多少层”，转移变成简单的加法，复杂度与代码都更优。

解法 2：正向 DP + 决策单调性时间 O(k·n)，空间 O(n)

按题意定义 dp[e][j] 为 e 个蛋、j 层楼至少要扔几次。在第 x 层扔：碎了剩 dp[e-1][x-1]，没碎剩 dp[e][j-x]，所以 dp[e][j] = 1 + min over x of max(dp[e-1][x-1], dp[e][j-x])。前一项随 x 递增、后一项随 x 递减，最优的 x 在两者交点；而且 j 增大时交点只会右移。所以对每个 e，用一个只向右移的指针 x 扫完所有 j，只需保存上一行和当前行。

状态定义直接对应题意，是最自然的入手点；也可以用二分找交点（O(k·n log n)）。但即使用了单调性仍是 O(k·n)，比主解法的 O(k·m) 慢很多（m 约为 log n 量级）。

class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        prev = list(range(n + 1))
        for _ in range(2, k + 1):
            cur = [0] * (n + 1)
            x = 1
            for j in range(1, n + 1):
                while x < j and max(prev[x], cur[j - x - 1]) <= max(prev[x - 1], cur[j - x]):
                    x += 1
                cur[j] = 1 + max(prev[x - 1], cur[j - x])
            prev = cur
        return prev[n]

class Solution {
    public int superEggDrop(int k, int n) {
        int[] prev = new int[n + 1];
        for (int j = 0; j <= n; j++) prev[j] = j;
        for (int e = 2; e <= k; e++) {
            int[] cur = new int[n + 1];
            int x = 1;
            for (int j = 1; j <= n; j++) {
                while (x < j && Math.max(prev[x], cur[j - x - 1]) <= Math.max(prev[x - 1], cur[j - x])) x++;
                cur[j] = 1 + Math.max(prev[x - 1], cur[j - x]);
            }
            prev = cur;
        }
        return prev[n];
    }
}

class Solution {
public:
    int superEggDrop(int k, int n) {
        vector<int> prev(n + 1);
        for (int j = 0; j <= n; j++) prev[j] = j;
        for (int e = 2; e <= k; e++) {
            vector<int> cur(n + 1, 0);
            int x = 1;
            for (int j = 1; j <= n; j++) {
                while (x < j && max(prev[x], cur[j - x - 1]) <= max(prev[x - 1], cur[j - x])) x++;
                cur[j] = 1 + max(prev[x - 1], cur[j - x]);
            }
            prev = cur;
        }
        return prev[n];
    }
};

func superEggDrop(k int, n int) int {
	prev := make([]int, n+1)
	for j := 0; j <= n; j++ {
		prev[j] = j
	}
	for e := 2; e <= k; e++ {
		cur := make([]int, n+1)
		x := 1
		for j := 1; j <= n; j++ {
			for x < j && max(prev[x], cur[j-x-1]) <= max(prev[x-1], cur[j-x]) {
				x++
			}
			cur[j] = 1 + max(prev[x-1], cur[j-x])
		}
		prev = cur
	}
	return prev[n]
}

var superEggDrop = function(k, n) {
    let prev = Array.from({ length: n + 1 }, (_, j) => j);
    for (let e = 2; e <= k; e++) {
        const cur = new Array(n + 1).fill(0);
        let x = 1;
        for (let j = 1; j <= n; j++) {
            while (x < j && Math.max(prev[x], cur[j - x - 1]) <= Math.max(prev[x - 1], cur[j - x])) x++;
            cur[j] = 1 + Math.max(prev[x - 1], cur[j - x]);
        }
        prev = cur;
    }
    return prev[n];
};

function superEggDrop(k: number, n: number): number {
    let prev = Array.from({ length: n + 1 }, (_, j) => j);
    for (let e = 2; e <= k; e++) {
        const cur: number[] = new Array(n + 1).fill(0);
        let x = 1;
        for (let j = 1; j <= n; j++) {
            while (x < j && Math.max(prev[x], cur[j - x - 1]) <= Math.max(prev[x - 1], cur[j - x])) x++;
            cur[j] = 1 + Math.max(prev[x - 1], cur[j - x]);
        }
        prev = cur;
    }
    return prev[n];
}

动态规划专题的其他题目

查看动态规划全部题目 →