主題
題目連結：
題目意譯：
我們現在玩一個猜猜樂遊戲。該遊戲將會按照以下流程遊玩：
1. 我從 1 到 n 之間選出某個數字。
2. 你猜某個數字。
3. 如果你猜對數字，則你贏。
4. 如果你猜錯數字，則我將會告訴你我選的數字相對於你的數字是比較大還是小。而你將會繼續猜數字。
5. 每一次你猜 x 而且猜錯了，你將會付 x 元。如果你沒錢了，則你輸。
給定一個 n 值，回傳你在無論我挑什麼數字都可以贏的情況下所需的最小金額。
限制：
1 ≦ n ≦ 200
範例測資：
範例 1：
輸入： n = 10
輸出： 16
解釋： 必贏策略如下：
- 範圍為 [1,10]。你猜 7。
- 如果這是我選的數字，你總共付 0 元。反之，你將多付 7 元。
- 如果我選的數字比較大，則範圍為 [8,10]。你猜 9。
- 如果這是我選的數字，你總共付 7 元。反之，你將多付 9 元。
- 如果我選的數字比較大，則其必為 10。你猜 10。你總共付 7 + 9 = 16 元。
- 如果我選的數字比較小，則其必為 8。你猜 8。你總共付 7 + 9 = 16 元。
- 如果我選的數字比較小，則其範圍為 [1,6]。猜 3。
- 如果這是我選的數字，你總共付 7 元。反之，你將多付 3 元。
- 如果我選的數字比較大，則範圍為 [4,6]。你猜 5。
- 如果這是我選的數字，你總共付 7 + 3 = 10 元。反之，你將多付 5 元。
- 如果我選的數字比較大，則其必為 6。你猜 6。你總共付 7 + 3 + 5 = 15。
- 如果我選的數字比較小，則其必為 4。你猜 4。你總共付 7 + 3 + 5 = 15。
- 如果我選的數字比較小，則其範圍為 [1,2]。你猜 1。
- 如果這是我選的數字，你總共付 7 + 3 = 10 元。反之，你將多付 1 元。
- 如果我選的數字比較大，則其必為 2。你猜 2。你總共付 7 + 3 + 1 = 11 元。
在所有可能的情況下中你最糟會付 16 元。因此你只需要 16 元來保證你會贏。
範例 2：
輸入： n = 1
輸出： 0
解釋： 現在只有一種可能的數字可以挑，所以你可以直接猜 1 並且不用付任何錢。
範例 3：
輸入： n = 2
輸出： 1
解釋： 現在有兩種可能的數字，1 和 2。
- 你猜 1。
- 如果這是我選的數字，你總共付 0 元。反之，你將多付 1 元。
- 如果我選的數字比較大，則其必為 2。你猜 2。你總共付 1 元。
最糟情況下你將付 1 元。
解題思維：
可以看到如果現在數字範圍是 [L, R]，而你現在猜了一個數字 x，其中 L ≦ x ≦ R。則你會產生出三個可能的分支：
1. x 就是我選的數字；
2. 我選的數字實際上是在 [L, x - 1]；
3. 我選的數字實際上是在 [x + 1, R]。
而由於你要應付所有可能的情況，因此你在 [L, R] 時猜 x 的「成本」（即題目提及的最小所需金額）將會是 max([L, x - 1] 時所需的最小成本, [x + 1, R] 時所需的最小成本)。
而這樣子的 x 值可能很多個，所以子問題也會跟著會有很多個。不知道要做哪些？那就全做吧！這基本上就是動態規劃（Dynamic Programming）的精神。
定義一個二維陣列 D，其中 D[i][j] 代表著現在數字範圍為 [i, j] 的情況下最小所需的金額。根據以上的觀察，可以看到其遞迴式為：
D[i][j] = 0，其中 i ≧ j
（上式為遞迴的停止條件）
D[i][j] = min(max(D[i][x - 1], D[x + 1][j]) + x)，其中 i ≦ x ≦ j
遞迴求完之後，最後所求位於 D[1][n]。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
