解題說明
Guess Number Higher or Lower II
題目描述：從 1 到 n 中選一個數字，你每次猜一個數 x，若猜錯需付 x 元。求在最壞情況下保證能猜中所需的最少金額。
解題思路：這是一個極小化極大（Minimax）問題。定義 dp[i][j] 為在 [i, j] 範圍內保證猜中所需的最少金額。對於每個可能的猜測 k (i <= k <= j)，最壞情況的花費為 k + max(dp[i][k-1], dp[k+1][j])。我們要在所有可能的 k 中選擇讓最壞花費最小的：dp[i][j] = min over k of { k + max(dp[i][k-1], dp[k+1][j]) }。使用區間 DP，按區間長度由小到大填表。
C++ 解法
複雜度分析
時間複雜度：O(n^3) — 三層迴圈：區間長度 O(n)、起點 O(n)、猜測位置 O(n)。
空間複雜度：O(n^2) — DP 表格大小為 n x n。
虛擬碼
1. Create dp[n+2][n+2] initialized to 0
2. For length = 2 to n:
a. For each start i where i + length - 1 <= n:
- j = i + length - 1
- dp[i][j] = infinity
- For each guess k from i to j:
- cost = k + max(dp[i][k-1], dp[k+1][j])
- dp[i][j] = min(dp[i][j], cost)
3. Return dp[1][n]其他解法
記憶化遞迴 O(n^3)：自頂向下的 DFS + memo，思路與動態規劃相同但用遞迴實作。程式碼可能更直觀易讀，但有遞迴堆疊開銷。
二元搜尋啟發式：直覺上每次猜中間可能最好，但這不是最優策略。因為猜的數字本身就是代價，所以最優猜測點通常偏向右側（較高的數字代價更大，應先排除）。此啟發式無法保證最優但可作為理解的起點。
延伸思考
- 如果猜錯的代價不是 x 而是固定常數 c，問題會變成什麼？（提示：二元搜尋）
- dp[i][j] 的最優猜測點 k 是否具有單調性？能否利用此性質將時間優化到 O(n^2)？
- 這個問題與最優二元搜尋樹（Optimal BST）有何關聯？