九章演算法 | 快手面試題：丟雞蛋Ⅱ
【題目描述】
有一個
n
層的建築。如果一個雞蛋從第
k
層及以上落下，它會碎掉。如果從低於這一層的任意層落下，都不會碎。
有
m
個雞蛋，用最壞的情況下實驗次數最少的方法去找到k， 返回最壞情況下所需的實驗次數。
線上評測地址： LintCode 領釦
Example 1：
Input： m = 2， n = 100
Output： 14
Example 2：
Input： m = 2， n = 36
Output： 8
【題解】
動態規劃。
dp［i］［j］代表從有i個雞蛋在第j層需要的最少次數。
轉移方程為
dp［i］［j］=min（dp［i］［j］，max（dp［i - 1］［k - 1］， dp［i］［j - k］））
即每次在第k層碎了所轉移到的狀態，以及第k層沒碎所轉移到的狀態
public
class
Solution
{
/**
* @param m the number of eggs
* @param n the umber of floors
* @return the number of drops in the worst case
*/
public
int
dropEggs2
（
int
m
，
int
n
）
{
// Write your code here
int
［］［］
dp
=
new
int
［
m
+
1
］［
n
+
1
］；
for
（
int
i
=
1
；
i
<=
m
；
++
i
）
{
dp
［
i
］［
1
］
=
1
；
dp
［
i
］［
0
］
=
0
；
}
for
（
int
j
=
1
；
j
<=
n
；
++
j
）
dp
［
1
］［
j
］
=
j
；
for
（
int
i
=
2
；
i
<=
m
；
++
i
）
{
for
（
int
j
=
2
；
j
<=
n
；
++
j
）
{
dp
［
i
］［
j
］
=
Integer
。
MAX_VALUE
；
for
（
int
k
=
1
；
k
<=
j
；
++
k
）
{
dp
［
i
］［
j
］
=
Math
。
min
（
dp
［
i
］［
j
］，
1
+
Math
。
max
（
dp
［
i
-
1
］［
k
-
1
］，
dp
［
i
］［
j
-
k
］））；
}
}
}
return
dp
［
m
］［
n
］；
}
更多語言程式碼參見：九章演算法
