主題
題目連結(jié)：
題目意譯：
你被給定兩顆一模一樣的蛋，而你現(xiàn)在可以任意進(jìn)出一棟有 n 層樓且每層編號為 1 到 n 的建築物。
你知道存在一個(gè)樓層 f，其中 0 ≦ f ≦ n 使得任何蛋從 f 層樓以上（含）丟下將會破掉，而任何蛋從 f 層樓以下（不含）丟下將不會破掉。
在每一步之中，你可以拿一顆沒有破掉的蛋並從任意樓層 x（其中 1 ≦ x ≦ n）丟下。如果蛋破了，則你不得再使用它。不過如果蛋沒破，則你可以在之後再次使用它。
回傳你確定可以保證決定出 f 值最少所需的步數(shù)。
限制：
1 ≦ n ≦ 1000
範(fàn)例測資：
範(fàn)例 1：
輸入： n = 2
輸出： 2
解釋： 我們可以從樓層 1 丟下第一顆蛋並從樓層 2 丟下第二顆蛋。
如果第一顆蛋破了，則我們得知 f = 0。
如果第二顆蛋破了但第一顆蛋沒有破，則我們得知 f = 1。
而如果兩顆蛋都存活下來，則我們得知 f = 2。
範(fàn)例 2：
輸入： n = 100
輸出： 14
解釋： 其中一個(gè)最佳策略為：
- 將第一顆蛋從樓層 9 丟下。如果它破了，則我們得知 f = 0 到 8 之間。把第二顆蛋從樓層 1 開始（含）一層一層往上來依序丟下這顆蛋來在額外 8 步之內(nèi)找到 f 值。總次數(shù)為 1 + 8 = 9。
- 如果第一顆蛋沒有破，則將第一顆蛋從樓層 22 丟下。如果它破了，則我們得知 f = 9 到 21 之間。把第二顆蛋從樓層 9 開始（含）一層一層往上來依序丟下這顆蛋來在額外 12 步之內(nèi)找到 f 值。總次數(shù)為 2 + 12 = 14。
- 如果第一顆蛋又沒有破，則將重複類似的過程來從樓層 34 、 45 、 55 、 64 、 72 、 79 、 85 、 90 、 94 、 97 、 99 和 100 丟下第一顆蛋。
不管結(jié)果如何，最多需要 14 步才能決定 f 值。
解題思維：
以前有一篇解題心得是類似於本題且範(fàn)圍更廣（「蛋數(shù)」更多），參見這題。
而根據(jù)該題的遞迴式，我們可以看到我們的遞迴式固定為 D[2][j]（之後將用此格式來替代「D2, j」，其他的也是類似） = D[2][j - 1] + D[1][j - 1] + 1，而我們想要找到最小的 j 值使得 D[2][j] ≧ n。
可以看到 D[1][j] 之值即為 j。因此我們可以上面的遞迴式替換成 D[2][j] = D[2][j - 1] + j。
接著我們?nèi)绻恢闭归_遞迴式，最後我們可以得到 D[2][j] = 1 + 2 + …… + j = (j + 1) × j ÷ 2。
接著我們可以從 j = 1 開始（含）遞增直到找到第一個(gè) j 值滿足 (j + 1) × j ÷ 2 ≧ n。又或者我們可以照著這題的作法來直接計(jì)算出所求 j 值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達(dá)人
