題目網址：https://leetcode.cn/problems/guess-number-higher-or-lower-ii/

題意：我們正在玩一個猜數遊戲, 遊戲規則如下：

  1. 我從 1 到 n 之間選擇一個數字
  2. 你來猜我選了哪個數字
  3. 如果你猜到正確的數字, 就會贏得遊戲
  4. 如果你猜錯了, 那麽我會告訴你, 我選的數字比你的更大 or 更小, 並且你需要繼續猜數
  5. 每當你猜了數字 x 並且猜錯了的時候, 你需要支付金額為 x 的現金。如果你花光了錢, 就會輸掉遊戲。

給你一個特定的數字 n, 返回能夠確保你獲勝的最小現金, 不管我選擇哪個數字。

Solution：

想法：利用 DP

1. 定義狀態：

  • dp[i][j]：區間 [i, j] 中確保獲勝的最小現金

2. 得到轉移方程：

  • 選 k 且猜錯, 則確保獲勝的最小金額為 k + max(dp[i][k - 1, dp[k + 1][j])。
    ➔ 取兩個區間中的最大值是因為要確保必須考慮最差情況
  • dp[i][j] = min(dp[i][j], k + max(dp[i][k - 1], dp[k + 1][j])), for i ≤ k ≤ j

3. 初始化：

  • dp[0][0]：沒有數時, 確保獲勝的最小現金為 0
  • dp[i][i]：當區間中只有一個數時, 確保獲勝的最小現金為 0。其中, 1 ≤ i ≤ n

注意：

  • dp 的長度之所以要開 n + 2 而非 n + 1, 是因為 i ≤ k ≤ j
    ➔ dp[k + 1][j] 中的 k + 1 最多是 n + 1, 故長度開 n + 2
  • 當 k + 1 > n 時, dp[k + 1][j] 的值為 0
    ➔ 根據 dp[i][j] 的定義, dp[k + 1][j] 為空區間, 故設為 0
class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

        for (int i = 0; i <= n; ++i) {
            dp[i][i] = 0;
        }

        for (int len = 2; len <= n; ++len) {
            for (int i = 1; i + len - 1 <= n; ++i) {
                const int j = i + len - 1;
                dp[i][j] = INT_MAX; // 要取最小值, 故將初始值設最大

                for (int k = i; k <= j; ++k) {
                    dp[i][j] = min(dp[i][j], k + max(dp[i][k - 1], dp[k + 1][j]));
                }
            }
        }

        return dp[1][n];
    }
};
  • time：$O(n^3)$ ➔ for loop
  • space：$O(n^2)$ ➔ dp