Guess Number Higher or Lower II
Medium · 1-D Dynamic Programming · Explanation and code example
Memoized Minimax on Intervals
How it works
For a guess k, an incorrect answer costs k plus the cost of the remaining interval. To guarantee a win, account for the more expensive side. Try every guess and choose the minimum of these worst-case costs; an interval with at most one value needs no payment.
Steps
- Memoize the guaranteed cost for each interval.
- For every possible guess, add its value to the maximum cost of the two remaining sides.
- Take the minimum candidate cost.
Complexity
- Time: O(n³).
- Space: O(n²) memo plus O(n) recursion stack.
Things to watch for
- Take the maximum over outcomes, then the minimum over guesses.
- A correct guess costs zero.
- The single-value base case is zero, rather than the value itself.
Python code example
import functools
class Solution:
def getMoneyAmount(self, n: int) -> int:
@functools.lru_cache(None)
def dp(i: int, j: int) -> int:
"""Returns the minimum money you need to guarantee a win of picking i..j.
"""
if i >= j:
return 0
return min(max(dp(i, k - 1), dp(k + 1, j)) + k
for k in range(i, j + 1))
return dp(1, n)
C++ code example
class Solution {
public:
int getMoneyAmount(int n) {
vector<vector<int>> mem(n + 1, vector<int>(n + 1, INT_MAX));
return getMoneyAmount(1, n, mem);
}
private:
// Returns the minimum money you need to guarantee a win of picking i..j.
int getMoneyAmount(int i, int j, vector<vector<int>>& mem) {
if (i >= j)
return 0;
if (mem[i][j] != INT_MAX)
return mem[i][j];
for (int k = i; k <= j; ++k)
mem[i][j] = min(mem[i][j], max(getMoneyAmount(i, k - 1, mem),
getMoneyAmount(k + 1, j, mem)) +
k);
return mem[i][j];
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.