描述
题目描述
一座大楼有 n+1 层，地面算作第0层，最高的一层为第 n 层。已知棋子从第0层掉落肯定不会摔碎，从第 i 层掉落可能会摔碎，也可能不会摔碎。
给定整数 n 作为楼层数，再给定整数 k 作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋子。
要求：空间复杂度 O(k)，时间复杂度 O(km)(m是最终返回的结果)
示例
输入：10,1
返回值：10
说明：
因为只有1棵棋子，所以不得不从第1层开始一直试到第10层，在最差的情况下，即第10层是不会摔坏的最高层，最少也要扔10次
知识点：动态规划、递归、数组
难度：⭐⭐⭐⭐
题解
方法一：动态规划（超时）
图解
最差情况：棋子在第i层楼碎没碎，取决于没碎和碎了的情况下的更大结果
最小次数：可以理解为尝试在所有楼层1 <= i <= N扔棋子，每次选择尝试次数最少的那一层
状态转移：其中 dp(2, 8) 表示当前还有2个棋子，需要测试的层数为8
- 如果棋子碎了，那么棋子的个数
K应该减一，搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼； - 如果棋子没碎，那么棋子的个数
K不变，搜索的楼层区间应该从[1..N]变为[i+1..N]共N-i层楼。
因为我们要求的是最坏情况下扔棋子的次数，所以棋子在第i层楼碎没碎，取决于没碎和碎了的情况下的更大结果，即：
// 伪代码：
for(int i = 1; i <= N; i++) {
res = Math.min(res, // min：第一层到第 N 层的最少扔棋子次数
Math.max( // max：当前层 i 的扔棋子最坏情况
dp(K - 1, i - 1), // 碎
dp(K, N - i) // 没碎
) + 1) // 在第 i 楼扔了一次
}
算法流程
1、暴力穷举尝试在所有楼层1 <= i <= N扔棋子，每次选择尝试次数最少的那一层；
2、每次扔棋子有两种可能，要么碎，要么没碎；
3、如果棋子碎了，结果层数 F 应该在第i层下面，否则，F应该在第i层上面；
4、棋子是碎了还是没碎，取决于哪种情况下尝试次数更多，因为我们想求的是最坏情况下的结果。
Java 版本代码如下：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回最差情况下扔棋子的最小次数
* @param k int整型 棋子数
* @param n int整型 楼层数
* @return int整型
*/
int[][] memo;
public int solve (int n, int k) {
memo = new int[k + 1][n + 1];
for(int[] m : memo) {
Arrays.fill(m, -1);
}
return dp(k, n);
}
// 定义：有K个棋子面对N层楼，最少需要扔 dp(K, N) 次
int dp(int k, int n) {
// 状态：棋子数k，需要测试的楼层n
if(k == 1) {
return n;
}
// 尝试到底层
if(n == 0) {
return 0;
}
if(memo[k][n] != -1) {
return memo[k][n];
}
int res = Integer.MAX_VALUE;
// 寻找第一层到第n层的最少扔的次数
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;
}
}
复杂度分析：
时间复杂度：dp函数本身复杂度是 O(N)，子问题个数为 O(kn)，因此总时间复杂度是 O(K*N^2)
空间复杂度：空间复杂度为子问题个数 O(KN)，以及递归需要的栈空间，以及记忆化搜索需要的备忘录二维数组 O(nk)
方法二：动态规划+二分搜索优化（超空间）
算法过程：
Java 版本代码如下：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回最差情况下扔棋子的最小次数
* @param k int整型 棋子数
* @param n int整型 楼层数
* @return int整型
*/
int[][] memo;
public int solve (int n, int k) {
memo = new int[k + 1][n + 1];
for(int[] m : memo) {
Arrays.fill(m, -1);
}
return dp(k, n);
}
int dp(int k, int n) {
// 状态：棋子数k，需要测试的楼层n
if(k == 1) {
return n;
}
// 尝试到底层
if(n == 0) {
return 0;
}
if(memo[k][n] != -1) {
return memo[k][n];
}
int res = Integer.MAX_VALUE;
int lo = 1, hi = n;
while(lo <= hi) {
int mid = lo + ((hi - lo) >> 1);
int broken = dp(k-1, mid-1);
int unBroken = dp(k, n-mid);
if(broken > unBroken) {
// 碎了，向下查找
hi = mid - 1;
// 最少次数
res = Math.min(res, broken + 1);
} else {
// 没碎，向上查找
lo = mid + 1;
res = Math.min(res, unBroken + 1);
}
}
memo[k][n] = res;
return res;
}
}
复杂度分析：
时间复杂度：二分搜索复杂度为O(logN)， 子问题个数为 O(KN)，因此总的时间复杂度为 O(KNlogN)
空间复杂度：O(KN)，维护了一个二维数组作为备忘录，以及递归调用栈的空间
方法三：状态转移改写（通过）
算法过程：
-
修改dp数组定义：确定当前的棋子个数和最多允许的扔棋子次数，就知道能够确定的最高楼层数。即之前两个方法的dp数组定义的一个「反向」版本
-
题目要求给你
k个棋子，n层楼，求最坏情况下最少的扔棋子次数j吗？while循环结束的条件是dp[K][j] == N，也就是给你K个棋子，允许扔j次，最坏情况下最多能测试n层楼。 -
最终要求的其实是扔棋子次数
j，但是这时候m在状态之中而不是dp数组的结果int j = 0; // 最多允许扔棋子个数 // dp[k][j]表示能够确定的最高楼层数，始终小于N while (dp[K][j] < N) { j++; // 状态转移... } return j; -
最后需要进行状态压缩，题目仅允许最多一维数组的空间，通过状态转移方程
dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1，可以发现dp[i][j]只和上面元素和左上面元素有关系， 故可以压缩一维：dp[i] = dp[i] + dp[i-1] + 1
未进行状态转移（超空间）：
import java.util.Arrays;
class Solution {
public int superEggDrop(int k, int n) {
// 确定当前的棋子个数i和最多允许的扔棋子次数j，就知道能够确定F的最高楼层数。
int[][] dp = new int[k + 1][n + 1];
// 棋子数为0，层数为0 (默认初始化为0，可不写)
for(int j = 0; j <= n; j++) {
dp[0][j] = 0;
}
// 允许扔棋子次数为0，层数为0 (默认初始化为0，可不写)
for(int i = 0; i <= k; i++) {
dp[i][0] = 0;
}
int j = 0;
while (dp[k][j] < n) {
j++;
for (int i = 1; i <= k; i++)
// 状态转移
dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1;
}
return j;
}
}
优化后的代码：
import java.util.*;
public class Solution {
public int solve (int n, int k) {
if(k == 1) {
return n;
}
if(n == 0) {
return 0;
}
// 相当于对最高楼层 n 进行二分查找，h相当于log2(n) + 1
int h = (int)(Math.log(n) / Math.log(2))+1;
// 如果k很大, 二分的扔即可，只是一种特殊情况
if(k > h) {
return h;
}
// dp数组定义：确定当前的棋子个数k，能够确定的最高楼层数h
int[] dp = new int[k];
// base case：没有棋子，最多测0层
dp[0] = 0;
// base case：只有一个棋子，最坏情况下最多只能测一层楼
dp[1] = 1;
// 统计扔的次数
int res = 1;
while(true){
// dp_i_1相当于dp[i-1]
int dp_i_1 = 0;
// 状态压缩后:
// dp[i] = dp[i] + dp[i-1] + 1
// 因为dp[i][j] 依赖的是左边和左上, 为了防止覆盖, 需要倒着计算
for(int i = 0; i < k; i++){
int temp = dp[i];
// 相当于dp[i] = dp[i] + dp[i-1] + 1, dp_i_1相当于dp[i-1]
dp[i] += dp_i_1 + 1;
// 保存作为下一次的dp[i-1]
dp_i_1 = temp;
// 能够确定到最高层 n, 返回结果
if(dp[i] >= n) {
return res;
}
}
// 每一轮迭代 次数增加1，相当于确定最高楼层n允许扔的次数
res++;
}
}
}
复杂度分析：
时间复杂度：总的时间复杂度为 O(KNlogN)
空间复杂度：O(K)，状态压缩后只用到了一维数组作为dp状态数组
京公网安备 11010502036488号