Guess Number Higher or Lower II - Medium - L
Published:
Question
- https://leetcode.com/problems/guess-number-higher-or-lower-ii/
We are playing the Guessing Game. The game will work as follows:
I pick a number between 1 and n.
You guess a number.
If you guess the right number, you win the game.
If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.
Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.
Approach
- DP
Solution
public class Solution {
public int getMoneyAmount(int n) {
int[][] dp = new int[n + 1][n + 1];
for (int len = 2; len <= n; len++) {
for (int start = 1; start <= n - len + 1; start++) {
int minres = Integer.MAX_VALUE;
for (int piv = start + (len - 1) / 2; piv < start + len - 1; piv++) {
int res = piv + Math.max(dp[start][piv - 1], dp[piv + 1][start + len - 1]);
minres = Math.min(res, minres);
}
dp[start][start + len - 1] = minres;
}
}
return dp[1][n];
}
}