现在是疫情期间，被动裁员，呆在宿舍没事儿做，在YouTube上看见了李永乐老师的一个双蛋问题的视频，就是众所周知的动态规划问题，然后就做了一下。

1，问题描述：

有t层楼，n个鸡蛋，鸡蛋是相同的，临界楼层是指从某个楼层之上抛下来，都会碎，但从这个楼层之下抛下来，都不会碎。没有碎的鸡蛋可以重复使用。试假设能找到这个临界楼层需要抛投的最少次数。

2，问题分析，画表格。

假设横轴为鸡蛋数，纵轴为楼层数，值为最少抛投次数。填表格。

这里要求的是能找到临界值至少抛投的次数。一看就是动态规划，直接找递归式。

设M(t,n)为在从t层楼，n个蛋的情况下需要抛投的最少次数，情况有多少种呢。当然是t种，从每一层都抛出一个鸡蛋试一下。

现在就要得到这t个抛投实验中的最小抛投次数。设Mk(t,n)为从k（1<=k<=t）层楼抛下1个鸡蛋进行测试而得到的抛投数。这t种抛投有通用的递推模式：

假设在k层楼进行抛投，会产生两种情况：

碎了：问题规模变为：M(k-1, n-1)

没碎：问题规模变为：M(t-k, n)

则Mk(t,n) = max(M(k-1, n-1), M(t-k, n)) + 1，也就是求出这种情况下最大的抛投次数。

而M(t,n)= min(M1(t,n), M2(t,n), M3(t,n) ...... Mk(t,n))

3，代码实验：

public class Egg {private int t;//t层楼private int n;//n个鸡蛋private int[][] m;//最优解，在（i(楼层)，j(鸡蛋)）时候的最优解。最优解是指，一定能找到临界楼层情况下的最少抛投次数。private Egg(int t, int n) {this.t = t;this.n = n;this.m = new int[t + 1][n + 1];// 舍弃零行零列的数据不要for (int[] ints : this.m) {for (int anInt : ints) {anInt = Integer.MAX_VALUE;// 全部初始化为最大值}}// 填充1行1列的简单数据for (int i = 1; i < t + 1; i++) {m[i][1] = i;//一层楼的话，至少试一次}for (int j = 1; j < n + 1; j++) {m[1][j] = 1;//一个鸡蛋的话，要试的次数为楼层数}}public int result() {//填充大于1行1列的空格for (int tt = 2; tt < t + 1; tt++) {//从第二层楼开始for (int nn = 2; nn < n + 1; nn++) {//从有两个鸡蛋开始int min = Integer.MAX_VALUE;for (int k = 1; k < t + 1 && tt > k; k++) {//第一次从k层楼抛切分min = Math.min(min, Math.max(m[tt - k][nn], m[k - 1][nn - 1]) + 1);// 如果失败，问题变为m[k-1][n-1]，如果成功，问题变为m[t-k][n]，现在每一层都切分一次，然后找到每一层切分需要的最大值。// 然后从每层楼中取最小值，这里要注意我们求的是什么：保证一定能找到临界楼层的最小抛投次数。}m[tt][nn] = min;}}return m[t][n];}public static void main(String[] args) {for (int i = 1; i < 26; i++) {System.out.print(i + " floors\t");for (int j = 1; j < 11; j++) {System.out.print(new Egg(i, j).result() + "\t");}System.out.println();}}
}

4，结果验证：

正确答案为：

是相同的。答案正确