887 – 鸡蛋掉落

887. 鸡蛋掉落

你将获得 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

提示

  • 1 <= K <= 100
  • 1 <= N <= 10000

题解

据说这是一道Google很经典的面试题qwq。

【TLE的DP】

  • 状态表示: dp[i][j] 表示当前状态为 i 个鸡蛋,面对 j 层楼,其中 1 <= i <= K, 1 <= j <= N
  • 状态转移:dp[k][n] = min{max{dp(K-1, i-1), dp(K, N-i)} + 1} ,其中 1 <= i <= N 。很好理解,遍历当前所处的层数 i ,如果在第 i 层扔鸡蛋,会出现两种情况:鸡蛋碎了,那么我们拿着剩下的 K - 1 个鸡蛋去 [1, i - 1] 楼层,也就是到了 dp[K-1][i-1] 状态;鸡蛋没碎,那么我们拿着剩下的 K 个鸡蛋去 [i + 1, N] 楼层,也就是到了 dp[K][N-i] 状态。
  • 记忆化:搜索的时候如果求出了某个 dp[K][N] ,就记忆化一下。

这样做复杂度是 O(N^2 · K) 的,愉快的TLE了,但还是放一下代码。

class Solution {
public:
    map<pair<int, int>, int> mp;
    int dfs(int k, int n) {
        if(k == 1) return n;
        if(n == 0) return 0;
        if(mp[make_pair(k, n)]) return mp[make_pair(k, n)] ;
        int ans = 0x3f3f3f3f;
        for(int i=1; i<=n; i++) {
            ans = min(ans, 1 + max(dfs(k, n-i), dfs(k-1, i-1)));
        }
        mp[make_pair(k, n)] = ans;
        return ans;
    }
    int superEggDrop(int K, int N) {
        mp.clear();
        return dfs(K, N);
    }
};

【二分+DP】

  • 优化:把TLE的方法中 O(n) 遍历寻找 dp[k][n] 最优解的方法改进为 O(nlogn) 的二分。
  • 二分:由上面的方法可以看到,状态转移方程为 dp[k][n] = min{max{dp(K-1, i-1), dp(K, N-i)} + 1} 。其中 dp[K-1][i-1]dp[K][N-i] 分别是关于 i 的单调递增和单调递减函数,所以二者必有一个交点,具体如下图。上一种方法是遍历求的这个点的,而现在我们可以使用二分。
  • 坑:一开始用的map发现TLE了,于是改成unordered_map,然后发现不能使用pair。脑子一转才意识到,用数组最快了……

代码码在这里~

int mp[105][10005];
class Solution {
public:    
    int dfs(int k, int n) {
        if(k == 1) return n;
        if(n == 0) return 0;
        if(mp[k][n] != -1) return mp[k][n];
        int ans = 0x3f3f3f3f;

        int left = 1, right = n;
        while(left <= right) {
            int mid = (left + right) >> 1;
            int broken = dfs(k - 1, mid - 1);
            int not_broken = dfs(k, n - mid);
            if(broken <= not_broken) {
                left = mid + 1;
                ans = min(ans, not_broken + 1);
            }
            else right = mid - 1;
        }
        mp[k][n] = ans;
        return ans;
    }

    int superEggDrop(int K, int N) {
        for(int i=0; i<=K; i++) for(int j=0; j<=N; j++) mp[i][j] = -1;
        return dfs(K, N);
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇