经典算法之鸡蛋掉落

经典算法之鸡蛋掉落

听说这是一道谷歌的经典算法题，虽然现在已经废弃了。总之，当我第一次看到这题，我满脑子问号。这什么呀我怎么连题目都看不懂，然后看了评论，还好不止我一个人哈哈哈哈。
ok先附上题目，有兴趣的朋友可以先做做看：来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/super-egg-drop

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中重复使用这枚鸡蛋。
请你计算并返回要确定 f 确切的值的最小操作次数是多少？

示例 1：
输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
如果它没碎，那么肯定能得出 f = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。

然后我结合官方题解去理解了这道题，终于搞懂了题目。不过其中有种解法很让我在意，但是我却有点懵，就是那种逆向思维解法。题目不是说K个鸡蛋在N层楼高，求最小操作f吗，但是逆向思维解法是，我现在有K个鸡蛋，有f种操作方法，最多我能探索几层楼。
Great！接下来看看怎么去用这种思想来解
先剧透一波，逆向思维需要用到的公式是这个f(t,k)=1+f(t−1,k−1)+f(t−1,k)
但我一直搞不懂为什么要“+1”。。
终于百度到一位博主的回答让我一下子豁然开朗！感谢！

以下思想来自：https://blog.csdn.net/whiteBearClimb/article/details/115701309?spm=1001.2101.3001.6650.13&utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-13.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-13.pc_relevant_default&utm_relevant_index=17
其实这道题很明显就是动归思想，而动归思想最基本的做法就是填表。所以当博主画了表格出来，真的就秒懂了！

首先，有K枚鸡蛋，C次操作数，可以探索的最大楼层数有多少，这里用F(K,C)表示

当只有一枚鸡蛋和无数次操作数，可以发现最大的探索层数是无限的（假设鸡蛋一直没有碎）
当只有一次操作数和无限个鸡蛋，可以探索的最大楼层数只有1，因为次数已经用完了
当然，没有鸡蛋或者没有次数时，探索层数肯定是0
这时，可以画出如下表格

	鸡蛋数1	鸡蛋数2	鸡蛋数3
操作数1	1	1	1
操作数2	2
操作数3	3

通过上面的信息可以得出上表，现在继续补充
当有2次操作数和2个鸡蛋时，假设现在在2楼扔鸡蛋
1.鸡蛋碎了，只剩下一个鸡蛋和一次操作数，根据之前的规律可以得到能探索的层数只有1（此时去三楼扔，如果没碎就能找到耐高楼层f=2，如果没碎那就只能是f>=3）
2.鸡蛋没碎，只剩下一次操作数和两个鸡蛋，根据之前的规律是只能探索一层（此时直接去3楼，因为去一楼没意义了，扔了之后如果碎了证明耐高楼层f=2，没碎f>=3）
所以总的来说，情况1+情况2+当前探索的一次 = 1+1+1 = 3
当有2次操作数和3个鸡蛋时，仍然在2楼扔鸡蛋
1.鸡蛋碎了，剩下2个鸡蛋和1次次数，根据刚刚得出的结论，可以探索1层
2.鸡蛋没有碎，剩下3个鸡蛋和1次次数，根据结论也是只有1层
结果也仍然是3层
所以可以得出次数只有两次，不管有几个鸡蛋，最多只能探索3次
补充表

	鸡蛋数1	鸡蛋数2	鸡蛋数3
操作数1	1	1	1
操作数2	2	3	3
操作数3	3

然后，当有3次次数和2个鸡蛋时，假设在2楼扔鸡蛋
1.鸡蛋碎了，剩1个鸡蛋和2次次数，根据上表可以得出有2层
2.鸡蛋没碎，剩2个鸡蛋和2次次数，根据上表可以得出有3层
总共：2+3+1=6
当有3次次数和3个鸡蛋时，继续在2楼扔（也许此时你已经发现跟在哪一层楼扔没有关系了）
1.鸡蛋碎了，剩2个鸡蛋2次次数，根据上表可以得到3层
2.鸡蛋没碎，剩3个鸡蛋2次次数，根据上表可以得到3层
总共：3+3+1 = 7
补表

	鸡蛋数1	鸡蛋数2	鸡蛋数3
操作数1	1	1	1
操作数2	2	3	3
操作数3	3	6	7

……
于是可以看到规律，F(K,C) = F(K-1,C-1) + F(K,C-1) + 1 (K>=2 && C>=2）

再次注意，现在我们求的是，在有K个鸡蛋，C次次数的情况下，最多可以探索多少层楼层
而leetcode的题是，在N层楼高的情况下，有K个鸡蛋，最少有几次就可以找到耐高楼层f。其实在逆转思路后，已经跟耐高楼层f没多大关系，问题就简化了。此外，所谓的操作数就是你上楼的次数，在N层楼的情况下，上楼次数即操作数也不能大于N
所以把刚刚的思路移动到此题中来就是

public int superEggDrop(int k, int n) {
    int[][] dp = new int[n + 1][k + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + 1;
            if (dp[i][j] >= n) {
                return i;
            }
        }
    }
    return n;
}

在看到这种解法前，我也看到了另一种解法，只是博主的解释我看不懂，但他的代码也可以套用到这里来

另一种写法：https://hestyle.blog.csdn.net/article/details/91996663?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&utm_relevant_index=1

再一次看上表，可以得到以下规律：
1.K =1时，F(K,C)=C
2.C=1时，F(K,C)=1
3.C=2时，F(K,C)=3
4.F(K,C) = F(K-1,C-1) + F(K,C-1) + 1 (K>=2 && C>=2）
所以也可以从C=1开始算起，当探索楼层<N时，C不断增加

//伪代码
while(F(K,C)<N){
    C++
}
return C

所以最后的完整代码如下：

public int superEggDrop(int k, int n) {
    int C = 1;
    while (getMaxSearchFloor(k, C) < n) {
        C++;
    }
    return C;

}

public int getMaxSearchFloor(int K, int C) {

    if (K == 1) {
        //一个鸡蛋情况下，探索楼层决定于次数
        return C;
    }
    if (C == 1) {
        //只有一次次数，只能探索一层
        return 1;
    }
    if (C == 2) {
        //当有两次次数，不管有多少个鸡蛋，也只能探索3层
        return 3;
    }
    //非上面两种情况
    return getMaxSearchFloor(K - 1, C - 1) + getMaxSearchFloor(K, C - 1) + 1;

}

啊终于完了，为了理解这题我花了快一个下午，因为很容易想着就偏了。不过最后理解了还是挺开心的，看来有时候真的用最简单的想法去解题反而是可以解决的。学到了学到了～

经典算法之鸡蛋掉落

感谢您的鼓励支持！