Guess Number Higher or Lower II
Medium
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.
题意
从1到n中猜数,每次猜不中扣掉等于所猜数目的钱,猜中数字不扣钱。问使用最优策略下最坏情况至少准备多少钱,一定可以猜中。
思路
动态规划。
dp[i][j]
表示在
[i, j]
区间中进行猜中数字至少要准备的钱。边界情况
dp[i][i] = 0
(区间中只有一个数,那么结果就是这个数,一定能猜中,不用扣钱)
递推公式
dp[i][j] = min(mid + max(dp[i][mid-1], dp[mid+1][j])), mid in [i, j]
其中
max
表示最坏情况,
min
表示最优策略
代码
class Solution {
public int getMoneyAmount(int n) {
int[][] dp = new int[n][n];
int i = 0, j = 0, mid = 0;
for (i=2; i<=n; ++i) {
for (j=0; j<=n-i; ++j) {
dp[j][i+j-1] = Integer.MAX_VALUE;
dp[j][i+j-1] = Math.min(Math.min(dp[j][i+j-1], j+1 + dp[j+1][i+j-1]), i+j + dp[j][i+j-2]);
for (mid = j+1; mid < i+j-1; ++mid) {
dp[j][i+j-1] = Math.min(dp[j][i+j-1], mid+1 + Math.max(dp[mid+1][i+j-1], dp[j][mid-1]));
}
}
}
return dp[0][n-1];
}
}