We are playing the Guess Game. The game is as follows:
I pick a number from 1to 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.
2. Implementation
(1) Memoization
class Solution {
public int getMoneyAmount(int n) {
int[][] cache = new int[n + 1][n + 1];
return getMoneyByDFS(1, n, cache);
}
public int getMoneyByDFS(int start, int end, int[][] cache) {
if (start >= end) {
return 0;
}
if (cache[start][end] != 0) {
return cache[start][end];
}
int cost = Integer.MAX_VALUE;
int mid = start + (end - start) / 2;
for (; mid <= end; mid++) {
cost = Math.min(cost, mid + Math.max(getMoneyByDFS(start, mid - 1, cache), getMoneyByDFS(mid + 1, end, cache)));
}
cache[start][end] = cost;
return cost;
}
}
(2) DP
class Solution {
public int getMoneyAmount(int n) {
// 因为数字从1开始，为了方便计算将dp维度变成 n + 1
// dp[i][j]代表在[i...j]这个区间里猜数字, 为了保证能赢而需要支付的最少花费
int[][] dp = new int[n + 1][n + 1];
for (int len = 1; len <= n; len++) {
for (int start = 1; start <= n - len + 1; start++) {
int end = start + len - 1;
// 当start等于end时，说明猜中数，不需要任何花费
if (start == end) {
continue;
}
dp[start][end] = Integer.MAX_VALUE;
for (int mid = start; mid < end; mid++) {
// 因为是要求的是保证能赢的情况，所以我们总是要考虑最坏的情况，所以我们[start, end]的区间枚举出可能猜中的数时，
// 在[start, mid - 1],[mid + 1, end]两个区间中，我们取得到花费较高的区间
dp[start][end] = Math.min(dp[start][end], mid + Math.max(dp[start][mid - 1], dp[mid + 1][end]));
}
}
}
return dp[1][n];
}
}