鸡蛋掉落
高级鸡蛋掉落是 DP 中"最坏情况最优"的经典问题。
// 算法讲解
鸡蛋掉落
用最少尝试次数确定鸡蛋从哪层楼掉落会碎。
待机
速度 中
待机 ⌨1int eggDrop(int k, int n) {
2 vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
3 for (int i = 1; i <= n; i++) dp[1][i] = i;
4 for (int i = 2; i <= k; i++) {
5 for (int j = 1; j <= n; j++) {
6 dp[i][j] = j;
7 for (int x = 1; x <= j; x++) {
8 dp[i][j] = min(dp[i][j], 1 + max(dp[i-1][x-1], dp[i][j-x]));
9 }
10 }
11 }
12 return dp[k][n];
13}
复杂度分析
时间 O(k * n * log n)
空间 O(k * n)
最优 O(k * n * log n)
最坏 O(k * n * log n)
算法讲解
给定 k 个鸡蛋和 n 层楼，用最少的尝试次数确定鸡蛋从哪层楼掉落会碎。
dp[k][n] 表示 k 个鸡蛋、n 层楼时的最少尝试次数。
转移：dp[k][n] = min(max(dp[k-1][x-1], dp[k][n-x]) + 1)，枚举 x 为当前尝试楼层。
时间复杂度 O(k * n * log n)，空间复杂度 O(k * n)。