2020/2/20

题目描述

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

示例

示例 1：
    输入：K = 1, N = 2
    输出：2
    解释：
        鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
        否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
        如果它没碎，那么我们肯定知道 F = 2 。
        因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。

示例 2：
    输入：K = 2, N = 6
    输出：3

示例 3：
    输入：K = 3, N = 14
    输出：4

相关标签

数学
二分查找
动态规划

解题思路

思路：
首先，对本题的题目描述进行进一步解释。假设，你现在在一幢高度为N=4大楼中（处于的楼层为[1， 2， 3， 4]）中的第2层，此时你扔下一枚鸡蛋，这会产生两种可能的结果：鸡蛋碎，或是不碎。如果鸡蛋碎了，那么说明在所有n>=2的楼层中扔下的鸡蛋都会碎；若果鸡蛋没碎，那么说明在所有n<2的楼层中，扔的鸡蛋都不会碎，并且你这一次尝试中扔出去的鸡蛋是可以被回收再利用的，也就是说鸡蛋数量k不会-1。我们要找到的就是这个分水岭楼层数F，即从F+1层开始扔的都会碎，1~F层扔的鸡蛋都不会碎。

然后就是如何理解所谓的 “ 无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？” 这句话。换一种说法，其实是在问我们在“最坏的情况下，用有限的鸡蛋最少能确定楼层F的最小尝试次数”。要理解这个问题，我们先来考虑一下在只有一个鸡蛋和有无限鸡蛋情况下不同的扔法。

1. 如果只存在一个鸡蛋，那么我们只能老老实实从1楼开始一层一层的向上推进，鸡蛋第一次碎的楼层即我们所寻找的楼层数F，此时所谓的最坏情况，即为这层楼的最高层N是我们想要找到的F，搜寻次数 t = N；
2. 如果存在无限多的鸡蛋，那么将楼层看做为一个性质有序的数列，我们可以采用二分搜索的方法来使用最小的次数找到目标楼层F。此时，搜寻次数为 |log2(N)|+1。

实际情况中，当1 < k < |log2(N)|+1 时，既不能全程采用二分搜索，也不需要从底层一层一层开始找，此时就需要采取混合策略来确定最小的尝试次数了，比如不断的采用二分，当发现鸡蛋数量不足时再逐楼层排查，最坏情况就可以理解为，当正好用完最后一个鸡蛋时，同时排查完楼层F的所有可能情况，最小尝试次数对应的便是这些所有可能的最坏情况中，尝试次数最小的一次。此时，就可以用上动态规划来做决策了。

动态规划 （方法一）+ 二分查找

• 算法：
  按照上述思路，我们已经整理出了第一类动态规划的大致思路。我们用 dp(k, n) 表示在k个鸡蛋和n层楼的条件下，最坏情况下的最小尝试次数 t 。
  可以得到如下递推关系式：

再加上备忘录消除重叠子问题，本题最基本的解法已经成形了。

复杂度分析：
函数本身的复杂度就是忽略递归部分的复杂度，这里 dp 函数中有一个 for 循环，所以函数本身的复杂度是 O(N)。
子问题个数也就是不同状态组合的总数，显然是两个状态的乘积，也就是 O(KN)。
所以算法的总时间复杂度是 O(K*N^2), 空间复杂度 O(KN)。

• 二分查找时间优化：
  在此之上，我们还可以采用二分查找来加快 a 情况中的最小值
  
  二分法求山顶值示意图（来源：labuladong）
  
  如图所示，我们可以通过选择在第 i 楼扔鸡蛋，将整栋大楼分为 [1, i - 1] 和 [ i + 1, N] 两部分。
  其中楼下的部分的最小尝试次数表示为dp(k-1, i-1)，楼上部分表示为dp(k, N-i)。
  比较容易证明，前者为单调上升，而后者单调下降，最终我们想要找到的是max(dp(k-1, i-1), dp(k, N-i)) 的最小值，也就是max(dp(k-1, i-1), dp(k, N-i)) 的函数图像的最低点（山顶/底点）。
  这一点可以通过求dp(k-1, i-1)与dp(k, N-i) 两条直线的交点来得到。搜索这个交点的过程便可以通过二分搜索来实现。具体实现见源代码。
  
  复杂度分析：
  优化后算法的总时间复杂度是 O(K *N *logN), 空间复杂度 O(KN)。效率上比之前的算法 O(KN^2) 要高效一些。

动态规划 （方法二）+ 迭代

• 算法：
  第二种动态规划的思路相较于第一种要难以理解一些。首先我们需要将原问题，即“有k个鸡蛋，N层楼，最坏情况下最少需要测几次”转换为“有k个鸡蛋，测t次，最多可以测完几层楼”，即从 dp(k, n) 转化为 dp(k, t)。当 t 从 1 不断增加，dp(k, t) 第一次 >= N 时，选取的 t 即 dp(k, n) 的答案。
  
  那么现在问题变成了如何来求取 dp(k, t)。现在想象自己正好处于一栋楼高为 dp(k, t) 的大楼中的某一层，你不知道你的楼下有多少层，也不知道你的楼上有多少层，此时你开始第一次测量，扔下了一枚鸡蛋，如果鸡蛋碎了，你就会去楼下继续测，你手上的鸡蛋数量减少了1，根据 dp 的定义，你最多可以在楼下测完 dp(k-1, t-1) 层楼；如果你的鸡蛋没有碎，呢么你就会去楼上测，那么你最多可以测完 dp(k, t-1) 层楼。现实中这两种情况都可能发生，所以楼上和楼下的楼层都是真实存在，且正好可以被测完的。再加上你所处于的这一层楼，最终得到整栋楼的高度为：

另外，当 k = 1 时，dp (k, t) = t, 即鸡蛋一直不碎，直到最后一次测完；
当 t = 1，k > 0 时，dp (k, t) = 1, 即只测一次只能测一层；

dp(k, t)的求解示意图（来源：labuladong）

• 复杂度分析:
  得到了递推关系式之后，我们便可以通过迭代或是递归的方法来进行求解，其中迭代法采用自底向上的方法来得到 F。
  在迭代法中，不存在函数调用，只存在 k 与 n 的两个循环，意味着其时间复杂度为O(KN)。
  空间复杂度方面，其需要一个大小为 K*N 的二维数组来存储子问题的结果，O(KN)。

动态规划 （方法二）+ 递归 + 二分查找 + HashMap

• 算法：上述的动态规划过程可以用递归法来实现，并采用二分来降低时间复杂度，此处我采用了每次取log2处的位置来缩小范围，比直接简单的对半分大部分情况下爱要高效很多，唯一需要注意的是k=1的情况下时间会比对半分来的更多，需要加上额外的条件判断来滤掉这种情况。此外，还采用HashMap来取代二维数组，节约了更多的空间。最终的运行结果及时间与空间消耗在源代码部分有对比。
• 复杂度分析:
  采用了二分之后，其时间复杂度一般情况下应当接近O(K logN)。
  空间复杂度方面，其需要一个大小为O(K logN)的HashMap来记录。这方面的计算不太确定。

源代码

动态规划 （方法一）+ 二分查找

use std::collections::HashMap;

impl Solution {    
    pub fn super_egg_drop(k: i32, n: i32) -> i32 {
        let mut map: HashMap<(i32, i32), i32> = HashMap::new();

        Self::drop_egg(k, n, &mut map)
    }

    pub fn drop_egg(k: i32, n: i32, m: &mut HashMap<(i32, i32), i32>) -> i32 {
        if let Some(ans) = m.get(&(k, n)) {
            return *ans;
        }
        if k == 1 {
            return n;
        }

        let min = ((n as f32).log2() as i32) + 1; 
        if k >= min {
            return min;
        }
        
        let (mut left, mut right) = (1, n-1);
        let res = loop {
            let mid = left + (right - left) / 2;
            let (broken, unbroken) = (Self::drop_egg(k-1, mid, m), Self::drop_egg(k, n-mid-1, m));
            if right - left <= 1 {
                break std::cmp::max(broken, unbroken) + 1;
            }     
            if broken == unbroken {
                break broken + 1;
            }else if broken < unbroken {
                left = mid;
            }else {
                right = mid;
            }
        };
             
        m.insert((k, n), res);
        res
    }   
}

执行用时 : 60 ms, 在所有 Rust 提交中击败了40.00%的用户
内存消耗 : 2.7 MB, 在所有 Rust 提交中击败了50.00%的用户

动态规划 （方法二）+ 迭代

use std::collections::HashMap;

impl Solution {    
    pub fn super_egg_drop(k: i32, n: i32) -> i32 {
        let mut dp: Vec<Vec<i32>> = vec![vec![0;(n+1) as usize];(k+1) as usize];
        let (mut hit, mut call) = (0, 0);
        let (mut _k, mut _t) = (1, 0);
        
        let t = loop {
            _t += 1;
            while _k as i32 <= k {
                call += 1;
                if _k == 1 {
                    dp[_k][_t] = _t as i32;
                }else {
                    dp[_k][_t] = dp[_k][_t-1] + dp[_k-1][_t-1] + 1;
                }
                _k += 1;
            }
            if dp[_k-1][_t] >= n {
                break _t;
            }
            _k = 1;
        };
        t as i32
    }   
}

执行用时 : 0 ms, 在所有 Rust 提交中击败了100.00%的用户
内存消耗 : 5.1 MB, 在所有 Rust 提交中击败了50.00%的用户

注：由于整型溢出和内存限制，此处最多只能取到（1000,100000）前后。

动态规划 （方法二）+ 递归 + 二分查找 + HashMap

use std::collections::HashMap;

impl Solution {    
    pub fn super_egg_drop(k: i32, n: i32) -> i32 {
        let mut dp: HashMap<(usize, usize), u64> = HashMap::new();
        let (mut left, mut right) = (1, n+1);
        if k == 1 {
            return n;
        }
        
        let t = loop {
            let mid = left + (right as f32- left as f32).log2() as i32;
            let floor = Self::drop_egg(k as usize, mid as usize, &mut dp);
            if floor > n as u64{
                right = mid;
            }else if floor < n as u64{
                left = mid+1;
            }else {
                break mid;
            }
            if left == right {
                break left;
            }
        };
        t as i32
    }

    pub fn drop_egg(k: usize, t: usize, dp: &mut HashMap<(usize, usize), u64>) -> u64 {
        if let Some(floor) = dp.get(&(k, t)) {
            return *floor;
        }
        if k == 1 || t == 1{
            return t as u64;
        }
        let floor = Self::drop_egg(k, t-1, dp) + Self::drop_egg(k-1, t-1, dp) + 1;
        dp.insert((k, t), floor);
        floor
    }
}

执行用时 : 0 ms, 在所有 Rust 提交中击败了100.00%的用户
内存消耗 : 2.4 MB, 在所有 Rust 提交中击败了50.00%的用户

总结

在DP问题中，往往可以通过转换角度，重新寻找状态转移函数的方式来优化算法，另外二分搜索也是常用的工具。