We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8. First round: You guess 5, I tell you that it's higher. You pay $5. Second round: You guess 7, I tell you that it's higher. You pay $7. Third round: You guess 9, I tell you that it's lower. You pay $9. Game over. 8 is the number I picked. You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
Solution: DP
Use dp[l][r] to denote the min money to win the game if the current guessing range is [l, r], to guarantee a win, we need to try all possible numbers in [l, r]. Let say we guess K, we need to pay K and the game might continue if we were wrong. cost will be K + max(dp(l, K-1), dp(K+1, r)), we need max to cover all possible cases. Among all Ks, we picked the cheapest one.
dp[l][r] = min(k + max(dp[l][k – 1], dp[k+1][r]), for l <= k <= r.
Time complexity: O(n^3)
Space complexity: O(n^2)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: int getMoneyAmount(int n) { constexpr int kInf = 1e9; vector<vector<int>> cache(n + 2, vector<int>(n + 2, kInf)); function<int(int, int)> dp = [&](int l, int r) { int& ans = cache[l][r]; if (l >= r) return 0; if (ans != kInf) return ans; for (int x = l; x <= r; ++x) ans = min(ans, x + max(dp(l, x - 1), dp(x + 1, r))); return ans; }; return dp(1, n); } }; |
Python3
1 2 3 4 5 6 7 8 |
# Author: Huahua class Solution: def getMoneyAmount(self, n: int) -> int: @lru_cache(maxsize=None) def dp(l, r): return min([k + max(dp(l, k - 1), dp(k + 1, r)) for k in range(l, r + 1)]) if l < r else 0 return dp(1, n) |