🌀riba2534's Blog
凡事有交代,件件有着落,事事有回音
LeetCode 887 鸡蛋掉落(dp,记忆化搜索,二分)

题目链接:鸡蛋掉落

你将获得 K 个鸡蛋,并可以使用一栋从 1N 共有 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. 1 <= K <= 100
  2. 1 <= N <= 10000

思路

两种方法:

方法一:记忆化搜索+二分

dp[t][n]代表:有t层楼,n个鸡蛋,最少要扔多少次才可以确定临界值。现在定义一个k (1<=k<=t),我们从第k层扔下去一个鸡蛋,如果鸡蛋碎了,我们就要往低一点的楼层去找,则当前dp[t][n]状态是dp[k-1][n-1]+1(k-1的原因是第k层已经扔过了),如果鸡蛋没碎,我们要向上找,当前的状态dp[t][n]等价于dp[t-k][n]+1

因为我们考虑的是最坏情况下找到鸡蛋的次数,所以状态转移方程为,$dp[t][n]=max(dp[k-1][n-1],dp[t-k][n])+1$

那么问题来了,我们还有一个k没有确定,k的取值范围是(1<=k<=t),我们当然可以枚举一下所有的k然后在所有的k中取最小值(因为题目求的是最小移动次数),但是每次枚举全部的k,复杂度比较高$O(KN^2)$。

于是我们需要用二分来确定k,我们观察上面的状态转移方程:

  • dp[k-1][n-1],k增大的时候,楼层越高,则值越大
  • dp[t-k][n],k增大的时候,楼层越小,值越小

所以一个是单调递增的,另一个是单调递减的,所以我们要确定的k在他们的交汇点。也就是找到使得dp[t-k][n]<=dp[t-1][n-1]的最大的k。用了二分之后的时间复杂度降为:$O(KNlogN)$

方法二:dp

定义dp[k][step]代表由k个鸡蛋,通过移动step步所能到达的确定的最大楼层。则易得

  • dp[0][step]=0 : 0 个鸡蛋,不论走多少步,所能确定的最大楼层永远只是0
  • dp[k][1]=1 :不论有多少个鸡蛋,如果之走一步,那么只能确定最大1层楼。
  • dp[1][step]=step:只有一个鸡蛋时,能走到的最大楼层只能1层一层试,需要step次数。

根据以上条件,可以得到状态转移方程:

$$dp[k][step]=dp[k-1][step-1]+dp[k][step-1]+1$$

表示:当前楼层有k个鸡蛋,走了step步能确定的最大楼层数量是,丢了鸡蛋碎了走一步能确定的最大楼层(dp[k-1][step-1])+丢了鸡蛋没碎走一步所能确定的最大楼层(dp[k][step-1])+当前这一层丢了鸡蛋只能确定的层数1.时间复杂度为:$O(K*N)$

代码

方法一:记忆化搜索+二分

没用二分超时版:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
    // 返回有t层,n个鸡蛋的最小移动次数,k是枚举的中间楼层
    int dp[10000 + 50][100 + 50];
    int dfs(int t, int n)
    {
        if (~dp[t][n])
            return dp[t][n];
        if (t == 0 || n == 0)
            return 0;
        if (n == 1)
            return t;
        if (t == 1)
            return 1;
        int minn = INT_MAX;
        for (int k = 1; k <= t; k++)
        {
            minn = min(minn, max(dfs(k - 1, n - 1), dfs(t - k, n)) + 1);
        }
        return dp[t][n] = minn;
    }
    // K 代表鸡蛋个数,N 代表楼层数
    int superEggDrop(int K, int N)
    {
        memset(dp, -1, sizeof(dp));
        return dfs(N, K);
    }
};

把k二分后,AC版:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution
{
public:
    // 返回有t层,n个鸡蛋的最小移动次数,k是枚举的中间楼层
    int dp[10000 + 50][100 + 50];
    int dfs(int t, int n)
    {
        if (~dp[t][n])
            return dp[t][n];
        if (t == 0 || n == 0)
            return 0;
        if (n == 1)
            return t;
        if (t == 1)
            return 1;
        int l = 1, r = t;
        while (r - l > 1)
        {
            int mid = (l + r) >> 1;
            int ans1 = dfs(mid - 1, n - 1);
            int ans2 = dfs(t - mid, n);
            if (ans1 < ans2)
                l = mid;
            else if (ans1 > ans2)
                r = mid;
            else
                l = r = mid;
        }
        return dp[t][n] = 1 + min(max(dfs(l - 1, n - 1), dfs(t - l, n)),
                                  max(dfs(r - 1, n - 1), dfs(t - r, n)));
    }
    // K 代表鸡蛋个数,N 代表楼层数
    int superEggDrop(int K, int N)
    {
        memset(dp, -1, sizeof(dp));
        return dfs(N, K);
    }
};

方法二:dp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
public:
    // K个鸡蛋,N层楼
    int superEggDrop(int K, int N)
    {
        // dp[k][step]表示给k个鸡蛋,移动step步所能达到的最大层数
        vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
        for (int step = 1; step < N; step++)
        {
            dp[0][step] = 0;
            for (int k = 1; k <= K; k++)
            {
                dp[k][step] = dp[k][step - 1] + dp[k - 1][step - 1] + 1;
                if (dp[k][step] >= N)
                    return step;
            }
        }
        return N;
    }
};

最后修改于 2020-04-28

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。