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