菜鸡第一次看算法题，这篇笔记还是不要看比较好

题目

x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

为了减少测试次数，从每个厂家抽样3部手机参加测试。

某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

解决方案

这东西就是传统的扔鸡蛋问题。

二分法

通常使用此方法的前提是 鸡蛋个数 ≥ ⌈log₂M⌉ (M表示楼层个数)例如，9~16层楼在最坏情况下都需要多达 4 个鸡蛋才能得出结果。

倘若鸡蛋个数少，当只剩最后一个鸡蛋时，只能最保守地在一个较大的区间内逐层向上扔鸡蛋，显然会徒增尝试次数，不宜使用。

动态规划

动态规划思想是利用对已求解的重复子问题进行记忆化存储，然后避免重复计算，利用最优化原理得出结果。说人话就是粗暴地递归找。

此方法需要寻找“状态转移方程式”，并依此“倒推”求解

先设一个函数 f(m,n) m 表示楼层数(不是楼高)，n 表示鸡蛋数，返回值为最优解在最恶劣情况下需要尝试的次数。

假设第一个鸡蛋在 x 层 (1≤x≤m) 扔出，将出现两种情况：

1. 鸡蛋在 x 层抛出后碎了
2. 鸡蛋在 x 层抛出后没碎

鸡蛋碎了

显然接下来应从 (1≤y≤x-1) 层扔出鸡蛋，由于鸡蛋碎了，鸡蛋个数将 -1，同时尝试过一次了，所以尝试次数 +1

根据上面所设函数，可以将这种情况用同样的函数表示为 f(x-1, n-1) +1

鸡蛋没碎

由于鸡蛋没有碎，可以确保小于等于此层数的都没有问题，并且鸡蛋个数没有减少
剩余待测试层数为 m-x，可以用函数表示为 f(m-x, n) +1

这个函数描述在剩下 m-x 个楼层，n 个鸡蛋，返回值为最优解在最恶劣情况下需要尝试的次数。

为什么是 m-x ?

如果在思考这里的时候，代入的一个 x 值比较大，则容易在这里面绕进去。

受平时写业务代码的影响，此处的 f(m-x, n) 易被理解为具有判断鸡蛋是否摔碎的功能，但之前定义 f(a,b) 只是一个用于计算摔鸡蛋所需次数的函数，并非处理业务逻辑的函数，即并不是判断鸡蛋会不会摔碎的函数。

也就是说，尽管已经知道 在 m-x 层的鸡蛋并不会碎(业务逻辑)，但仍需假设鸡蛋会碎，并求出在 m-x 层、有 n 个鸡蛋时需要尝试多少次。

f 的第一个参数压根就不是表示楼高的，而是楼层的个数！个数！

得出公式

在从 x 层扔鸡蛋的条件下，此处尚不知道到底鸡蛋碎还是不碎是更加恶劣的情况(需要进一步尝试的次数多)，因此需要同时求出上述两种情况，并取最大者：

f(m,n)=max{ f(x-1, n-1)+1, f(m-x, n)+1 }

题设要求我们解出哪层(x)扔鸡蛋可以在最恶劣的情况下(上式)所得值最小，因此需要遍历x (1≤x≤m)，分别代入 1≤x≤m 求出值，取最小者，函数返回值即为最优解在最恶劣情况下需要尝试的次数，而使这个返回值成立的x即为所求x(即所求最优解)

综上，易得公式：

f(m,n)=min{ max{f(1-1, n-1)+1, f(m-1, n)+1}, max{f(2-1, n-1)+1, f(m-2, n)+1}, max{f(3-1, n-1)+1, f(m-3, n)+1}, ..., max{f(m-1, n-1)+1, f(m-m, n)+1} }

代码实现

以从 100 楼下落，持有 2 个鸡蛋为例

public class Main {
    private static final int Floor = 100;
    private static final int Egg = 2;

    private static int f(final int m, final int n) {
        int min = 0;
        boolean isInitialized = false;

        if (m == 0)
            return 0;

        for (int x = 1; x <= m; x++) {
            int result = Math.max(f(x-1, n-1)+1, f(m-x, n)+1);

            if(!isInitialized || min > result) {
                isInitialized = true;
                min = result;
            }
        }

        System.out.printf("progress: m=%d value=%d \n", m, min);
        return min;
    }

    public static void main(String[] args) {
        System.out.println("result: " + f(Floor, Egg));
    }
}

跑一下就可以发现，计算花费了大量的时间，这是由于递归的资源开销很大，时间复杂度大，因此效率较低，需要在上式的基础上进行优化。

不优化可以吗？原题 1000 层楼，3 个鸡蛋，我觉得跑到收卷也跑不完，更何况还是渣机。

简单的优化

尝试重新整理思路以改写成循环的形式。

首先绘制一张表格：

显然：

1. 在只有一个鸡蛋时，楼层数=尝试次数
2. 在只有一层楼时，不管多少个鸡蛋都只尝试一次
3. 0 层楼或 0 个鸡蛋时不需要尝试，尝试次数记为 0

使用上面的公式，算出2个鸡蛋时、不同层楼的情况，再算出3个鸡蛋时、不同层楼的情况。

求解过程略，但可以发现：求解需要用到上次求解的结果，例如，在求解2个鸡蛋2层楼时，需要用到0层楼2个鸡蛋、1层楼1个鸡蛋的结果。显然，这个表格的填充顺序应是从上到下、从左到右、填完一行到下一行。

根据公式 f(m,n)=max{ f(x-1, n-1)+1, f(m-x, n)+1 }
得出：表格坐标(m,n)的值为 max{(x-1, n-1)的值+1, (m-x, n)的值+1}

整理思路

整理一下上面的操作，可以分为下面的过程：

0. 建立一个二维数组模仿上面的表格保存结果
1. 对只有一个鸡蛋时直接返回楼层数，暂时将其他填充为最大尝试次数
2. 2个以上的鸡蛋时，首先枚举鸡蛋个数(n)
3. 枚举鸡蛋个数(n)时，枚举楼层数(m)
4. 枚举楼层数(m)时，枚举从哪层楼开始扔(x)
5. 枚举从哪层楼开始扔(x)时，算出这层楼的尝试次数
6. 对应“坐标”的值为尝试次数的最小者
7. 最终所求解为表格最右下角的那个值

写成代码：

import java.util.stream.IntStream;

public class Main {
    private static final int Floor = 1000;
    private static final int Egg = 3;

    private static int getMinDropEggTries(final int floorNum, final int eggNum) {
        if (floorNum < 1 || eggNum < 1)
            return 0;

        int[][] result = new int[eggNum+1][floorNum+1]; //坐标为 (鸡蛋，楼层)

        IntStream.range(1, floorNum+1).forEach(value -> result[1][value] = value);
        IntStream.range(1, eggNum+1).forEach(value -> result[value][1] = 1);

        IntStream.range(2, eggNum+1).forEach(egg ->
                IntStream.range(2, floorNum+1).forEach(floor ->
                        IntStream.range(1, floor+1).forEach(x -> {
                                    int value = Math.max(result[egg-1][x-1] + 1, result[egg][floor-x] + 1);

                                    if(result[egg][floor] == 0 || result[egg][floor] > value)
                                        result[egg][floor] = value;
                                })));

        return result[eggNum][floorNum];
    }

    public static void main(String[] args) {
        System.out.println("result: " + getMinDropEggTries(Floor, Egg));
    }
}

进一步优化

不难发现，int[][] result 实际上在后续计算中并没有使用，可以将其简化以降低空间复杂度。