【算法】Super Egg Drop 鸡蛋掉落

题目

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

给 K 个鸡蛋，一个 N 层的建筑，一定有个 F 层，使得在小于等于 F 层扔鸡蛋不会破碎，而在大于 F 层扔鸡蛋会破碎。求找到 F 层至少需要多少步。

解题思路

这个题意开始看的时候，"至少"(“minimum”)真的是看得我一头雾水，总觉得“至少”就是两步，导致好久没有转过来弯。
其实，所谓的”至少“是说，在最坏情况下，找到 F 值所需要走的最少步数，这样就可以覆盖比最坏情况稍微好的情况。
即是说，至少需要多少步，才能确认所有楼层 N ，以确保一定能找到 F 。

这里可以考虑用动态规划， dp[moves][k] 表示 k 个鸡蛋走 moves 步可以确认的楼层数。
假设第一步在 X 层，丢鸡蛋会有两个结果：

1. 鸡蛋碎了，则还剩下 k-1 个鸡蛋和 moves-1 步，剩余可确认的层数即 dp[moves - 1][k - 1]
2. 鸡蛋没碎，则还剩下 k 个鸡蛋和 moves-1 步，剩余可确认的层数即 dp[moves - 1][k]

再加上第一步锁确认的 X 层这 1 层，可得 dp[moves][k] = dp[moves - 1][k - 1] + dp[moves - 1][k] + 1
起始值，当有 0 个鸡蛋（k=0）或者走 0 步（moves=0）时，dp[moves][k] 的值为 0 ，为计算方便， dp 声明时所有的值均为 0 即可。

代码实现

Runtime: 12 ms
Memory: 20.5 MB

func superEggDrop(_ K: Int, _ N: Int) -> Int {
        //dp[moves][K] 表示 K 个鸡蛋走 moves 步可以确认的楼层数 初始值为0
        var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:K + 1),count:N + 1)
        var moves = 0
        //当 dp[moves][K] 的值等于 N 的时候，即找到了符合要求的 moves
        while(dp[moves][K] < N)
        {
            //moves +1 并遍历 1~K 来计算 dp[moves][k] 的值
            moves += 1
            for k in 1...K
            {
                //计算 dp[moves][k] 的值
                //假设第一步在 X 层，丢鸡蛋会有两个结果：
                //  1. 鸡蛋碎了，则还剩下 k-1 个鸡蛋和 moves-1 步，剩余可确认的层数即 dp[moves - 1][k - 1]
                //  2. 鸡蛋没碎，则还剩下 k 个鸡蛋和 moves-1 步，剩余可确认的层数即 dp[moves - 1][k]
                //所以 dp[moves][k] = dp[moves - 1][k - 1] + dp[moves - 1][k] + 1，加值 1 为第一步确认的 X 层
                dp[moves][k] = dp[moves - 1][k - 1] + dp[moves - 1][k] + 1
            }
        }
        //找到 moves 后返回结果
        return moves
    }

代码地址：https://github.com/sinianshou/EGSwiftLearning