10K's

问题

我们有k个鸡蛋，有n层楼需要测试，鸡蛋会刚好在某一层楼扔下摔碎。需要设计一个算法，用有限的鸡蛋找到测试n层楼至少需要的实验次数。鸡蛋在实验过程中没摔碎就可以继续用，碎了就碎了，总可用的鸡蛋数量减少一个。

解析

首先声明，这道题没想明白，看答案动态规划算法也没他明白。最后看到一个解法也没看明白。

最开始想的是我们先抛开鸡蛋的数量限制，有n层楼，找到刚好让鸡蛋摔碎的楼层。那最naive 的方法就是从下到上一层层尝试直到鸡蛋第一次摔碎。这时需要的实验次数是n。

那么我们可以想到用二分。最终的实验次数就会变成logN。那么logN就会比N要好一些。这个就是题目中至少的含义。

但是，鸡蛋数量有限制。所以上述方法可能需要一些修改。

子问题。这个地方没办法说如何联想到的。可以去看某一层的与前面的一层的结果的关系。那么根据题意，我们可以得出当前层做实验，鸡蛋碎了，可用鸡蛋减一，但是我们确定当前层的答案可以基于楼下的某个答案。如果鸡蛋没碎，那么我们确定当前层的答案可以基于楼上的某个答案。

那我们定义一个dp数组，第一个参数可以是需要测试的楼层数量（而非定义成测到第几层），二维是鸡蛋数量的限制。结果即dp[n][k]。

又因为题目中说确定（WIth certainty），那么我们考虑的是最坏情况。就是肯定能测出的情况。那么在碎与没碎的情况中选出测试次数较多的那一个选项。根据再去取这个值与dp当前的位置的最小值。

**初始化。**当鸡蛋为0的时候，结果都是0初始值。因为没有鸡蛋可以用于测试。当鸡蛋为1的时候，也只能测一次。当层数为1的时候，不管鸡蛋有几个，也只需要测试一次。

代码

自己写的代码没写出来，总是有错。更没用到大家后续的二分优化的一些思路。但是在网上看到一个答案但是也没看太明白怎么想的。

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K + 1][N + 1];
        int m = 0;
        while (dp[K][m] < N) {
            m++;
            for (int k = 1; k <= K; k++) {
                dp[k][m] = 1 + dp[k][m - 1] + dp[k - 1][m - 1];
            }
        }
        return m;
    }
}

留个债吧。

Problem

We have k eggs with n floors to test, and the eggs will happen to be dropped and broken on one floor. An algorithm needs to be designed to find the number of experiments needed to test n floors at least with a finite number of eggs. If the egg does not break during the experiment, it can continue to be used, and if it breaks, it breaks and the total number of available eggs is reduced by one.

Solution

First of all, I don't understand this question, and I don't understand the dynamic programming algorithm. The last thing I saw was a solution that I didn't understand either.

The first thing I thought was that we should put aside the limit on the number of eggs and find the floor that just allows the eggs to break. Then the most naive way is to try from bottom to top layer by layer until the egg breaks for the first time. The number of experiments required at this point is n.

Then we can think of dichotomizing. The final number of experiments will be logN, and logN will be better than N. This is what is meant by at least in the title.

However, there is a limit to the number of eggs. So the above method may need some modification.

Subproblem. There is no way to say how to associate this place. One can go to the relationship of a certain layer with the result of the previous layer. Then according to the question, we can conclude that the current layer does the experiment and the egg is broken and the available egg minus one, but we determine that the answer for the current layer can be based on one of the answers downstairs. If the egg is not broken, then we are sure that the answer of the current layer can be based on some answer from upstairs.

Then we define a dp array, the first parameter can be the number of floors to be tested (not defined as the number of floors to be tested), and the second dimension is the limit on the number of eggs. The result is that dp[n][k].

Again, since the question says certainty (WIth certainty), then we are considering the worst case. It is the case that can be measured for sure. Then choose the one with more tests among the broken and unbroken cases as the option. According to then go to take the minimum value of this value with the current position of dp.

**Initialization. **When the egg is 0, the result are 0 initial value. Because there are no eggs available for testing. When the egg is 1, it can also be measured only once. When the number of layers is 1, it also only needs to be tested once, regardless of how many eggs there are.

Code

The code that I wrote myself didn't work out and always had errors. More useless to everyone's subsequent dichotomous optimization of some ideas. But I saw an answer online but didn't see too much how to think about it.

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K + 1][N + 1];
        int m = 0;
        while (dp[K][m] < N) {
            m++;
            for (int k = 1; k <= K; k++) {
                dp[k][m] = 1 + dp[k][m - 1] + dp[k - 1][m - 1];
            }
        }
        return m;
    }
}

Leave a debt.