LEETCODE算法:887. Super Egg Drop

发表于 更新于 分类于 Waline： 阅读次数：

题目

You are given K eggs, and you have access to a building with N floors from 1 to N.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).

Your goal is to know with certainty what the value of F is.

What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?

Example 1:

Input: K = 1, N = 2 Output: 2 Explanation: Drop the egg from floor 1. If it breaks, we know with certainty that F = 0. Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1. If it didn't break, then we know with certainty F = 2. Hence, we needed 2 moves in the worst case to know what F is with certainty. Example 2:

Input: K = 2, N = 6 Output: 3 Example 3:

Input: K = 3, N = 14 Output: 4

Note:

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

题解

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
//递归，会超时
class Solution {
    int res[101][10001];
    int get_step_floor(int k,int n,int ff)
    {
        return (max(get_step(k-1,ff-1),get_step(k,n-ff)))+1;
    }
    int get_step(int k,int n)
    {
        int tmpans=10002;
        if(res[k][n]!=0) return res[k][n];
        for(int i=1;i<=n;i++)
        {
            tmpans=min(get_step_floor(k,n,i),tmpans);
        }
        res[k][n]=tmpans;
        return tmpans;
    }
public:
    int superEggDrop(int K, int N) {
        for(int i=0;i<10001;i++)
        {
            res[1][i]=i;
        }
        for(int i=0;i<101;i++)
        {
            res[i][1]=1;
            res[i][2]=2;
        }
        return get_step(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 {
    int res[101][10001];
public:
    int superEggDrop(int K, int N) {
        for(int i=0;i<10001;i++)
        {
            res[1][i]=i;
        }
        for(int i=0;i<101;i++)
        {
            res[i][1]=1;
            //res[i][2]=2;
        }
        for(int i=2;i<=K;i++)
        {//i当前鸡蛋数
            for(int j=2;j<=N;j++)
            {//当前层数
                int tmpmin=10002;
                for(int h=1;h<=j;h++)
                {
                   tmpmin=min(tmpmin,max(res[i-1][h-1],res[i][j-h]));
                }
                res[i][j]=tmpmin+1;
            }
        }
        return res[K][N];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    int res[101][10001];
public:
    int superEggDrop(int K, int N) {
        for(int i=1;i<=N;i++)
        {//i当前操作次数
            res[0][i]=0;
            for(int j=1;j<=K;j++)
            {//当前鸡蛋数
                res[j][i]=res[j][i-1]+res[j-1][i-1]+1;
                if(res[j][i]>=N) return i;
            }
        }
        return 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
30
31
32
33
//递归加二分查找，不会超时
class Solution {
    int res[101][10001];
    //unordered_map<int,int> memo;
    int dp(int k,int n)
    {
        if(res[k][n]==0)
        {
            int ans;
            if(0==n) ans=0;
            else if(1==k) ans=n;
            else{
                int l=1,h=n;
                while(l+1<h)
                {
                    int mid=(l+h)/2;
                    int t1=dp(k-1,mid-1);
                    int t2=dp(k,n-mid);
                    if(t1<t2) l=mid;
                    else if(t1>t2) h=mid;
                    else l=h=mid;
                }
                ans=min(max(dp(k-1,l-1),dp(k,n-l)),max(dp(k-1,h-1),dp(k,n-h)))+1;
            }
            res[k][n]=ans; 
        }
        return res[k][n];
    }
public:
    int superEggDrop(int K, int N) {
        return dp(K,N);
    }
};

官方题解

https://leetcode-cn.com/problems/super-egg-drop/solution/ji-dan-diao-luo-by-leetcode-solution/