今天是堅持每日一題打卡的第十七天

---

題目鏈接：https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/submissions/

---

題解匯總：https://zhanglong.blog.csdn.net/article/details/121071779

---

題目描述

我們正在玩一個猜數(shù)游戲，游戲規(guī)則如下：

我從 1 到 n 之間選擇一個數(shù)字。
你來猜我選了哪個數(shù)字。
如果你猜到正確的數(shù)字，就會 贏得游戲 。
如果你猜錯了，那么我會告訴你，我選的數(shù)字比你的 更大或者更小 ，并且你需要繼續(xù)猜數(shù)。
每當你猜了數(shù)字 x 并且猜錯了的時候，你需要支付金額為 x 的現(xiàn)金。如果你花光了錢，就會 輸?shù)粲螒?。
給你一個特定的數(shù)字 n ，返回能夠 確保你獲勝 的最小現(xiàn)金數(shù)，不管我選擇那個數(shù)字 。

示例 1：

輸入：n = 10
輸出：16
解釋：制勝策略如下：

• 數(shù)字范圍是 [1,10] 。你先猜測數(shù)字為 7 。
  • 如果這是我選中的數(shù)字，你的總費用為 $0 。否則，你需要支付 $7 。
  • 如果我的數(shù)字更大，則下一步需要猜測的數(shù)字范圍是 [8,10] 。你可以猜測數(shù)字為 9 。
    • 如果這是我選中的數(shù)字，你的總費用為 $7 。否則，你需要支付 $9 。
    • 如果我的數(shù)字更大，那么這個數(shù)字一定是 10 。你猜測數(shù)字為 10 并贏得游戲，總費用為 $7 + $9 = $16 。
    • 如果我的數(shù)字更小，那么這個數(shù)字一定是 8 。你猜測數(shù)字為 8 并贏得游戲，總費用為 $7 + $9 = $16 。
  • 如果我的數(shù)字更小，則下一步需要猜測的數(shù)字范圍是 [1,6] 。你可以猜測數(shù)字為 3 。
    • 如果這是我選中的數(shù)字，你的總費用為 $7 。否則，你需要支付 $3 。
    • 如果我的數(shù)字更大，則下一步需要猜測的數(shù)字范圍是 [4,6] 。你可以猜測數(shù)字為 5 。
      • 如果這是我選中的數(shù)字，你的總費用為 $7 + $3 = $10 。否則，你需要支付 $5 。
      • 如果我的數(shù)字更大，那么這個數(shù)字一定是 6 。你猜測數(shù)字為 6 并贏得游戲，總費用為 $7 + $3 + $5 = $15 。
      • 如果我的數(shù)字更小，那么這個數(shù)字一定是 4 。你猜測數(shù)字為 4 并贏得游戲，總費用為 $7 + $3 + $5 = $15 。
    • 如果我的數(shù)字更小，則下一步需要猜測的數(shù)字范圍是 [1,2] 。你可以猜測數(shù)字為 1 。
      • 如果這是我選中的數(shù)字，你的總費用為 $7 + $3 = $10 。否則，你需要支付 $1 。
      • 如果我的數(shù)字更大，那么這個數(shù)字一定是 2 。你猜測數(shù)字為 2 并贏得游戲，總費用為 $7 + $3 + $1 = $11 。
        在最糟糕的情況下，你需要支付 $16 。因此，你只需要 $16 就可以確保自己贏得游戲。

示例 2：

輸入：n = 1
輸出：0
解釋：只有一個可能的數(shù)字，所以你可以直接猜 1 并贏得游戲，無需支付任何費用。

示例 3：

輸入：n = 2
輸出：1
解釋：有兩個可能的數(shù)字 1 和 2 。

• 你可以先猜 1 。
  • 如果這是我選中的數(shù)字，你的總費用為 $0 。否則，你需要支付 $1 。
  • 如果我的數(shù)字更大，那么這個數(shù)字一定是 2 。你猜測數(shù)字為 2 并贏得游戲，總費用為 $1 。
    最糟糕的情況下，你需要支付 $1 。

提示：

1 <= n <= 200

---

思路

題目只給定了一個參數(shù) n，表示在數(shù)字 1 到 n 中選擇了一個數(shù)，我們需要猜中選中的數(shù)，而我們每次猜錯都要付出一定的代價，代價就是你猜錯的那個數(shù)，而我們需要求解的就是不管對方選擇了什么數(shù)，你猜錯的最小代價。

一開始，有些同學可能會想到使用二分法來求解，但是，并不可行，使用二分法只能保證你以最少的次數(shù)猜中，而不是最小的代價猜中，所以，需要轉(zhuǎn)換思路。

我們可以枚舉 1 到 n 中的每一個數(shù)，記為 x，分兩種情況：

假如 x 正好是選中的數(shù)，那么，付出的代價為 0；
假如 x 不是選中的數(shù)，那么，付出的代價為 x，然后，我們會得到提示，選中的數(shù)比 x 大還是比 x 小：
假如比 x 小，我們只要求得 1 到 x-1 的最小代價，再加上 x 就能得到猜 x 時的最小代價；
假如比 x 大，我們只要求得 x+1 到 n 的最小代價，再加上 x 就能得到猜 x 時的最小代價；
而選中的數(shù)有可能在 x 的左邊，也可能在 x 的右邊，為了保證我們能夠贏得游戲，我們需要備用的現(xiàn)金應該是左右兩邊的最小代價的最大值再加上 x 本身。
當我們枚舉完這些 x 后，取其中的最小值就是我們需要備用的現(xiàn)金。

所以，我們可以得到遞推公式：$f(1)(n)=mi{n}_{x=1}^n(max(f(1)(x?1),f(x+1)(n))+x)$

當然，遞推公式中存在若干重復計算， 我們可以設定一個m*n數(shù)組，將每次遞歸得到的結(jié)果存入，在計算新值時，如果數(shù)組中有此值，直接返回數(shù)組值，反之進行遞歸。

---

class Solution { private:static const int MAX_SIZE = 200 + 5;int memo[MAX_SIZE][MAX_SIZE]; public:int getMoneyAmount(int n) {return dfs(1, n);}int dfs(int start, int end) {if (start >= end) {return 0;}if (memo[start][end] != 0) {return memo[start][end];}int ans = 0x3fffffff;for (int k = start; k <= end; k++) {ans = min(ans, max(dfs(start, k - 1), dfs(k + 1, end)) + k);}return memo[start][end] = ans;} };

總結(jié)

以上是生活随笔為你收集整理的C++题解-Leecode 375. 猜数字大小 II——Leecode每日一题系列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。