描述

题目描述

一座大楼有 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状态数组