LeetCode Guess Number Higher or Lower

· 503 words · 2 minute read
2017年6月
LeetCode-动态规划

375. Guess Number Higher or Lower II

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,2,3,4，只取1,3的值要小于由二分法求得的只取2,3的值。说明中间k不一定等于(start+end)/2，start<= k <= end。得用动态规划。

定义:dp[i][j]为在区间[i,j]中保证赢需要多少最少的钱。

目标:dp[1][n]

边界条件：dp[i][i] = 0

状态转换方程:dp[i][j] = Math.min(dp[i][j],k + Math.max(dp[i][k-1],dp[k+1][j])) (k-1 >= i, k+1 <= j)其中k表示花了k钱。

需要从底往上运算,如下:

dp矩阵举例：
(1,1) (1,2) (1,3) ==> (1,2)和(2,3) (1,4) ==> (1,3)和(3,4)
      (2,2) (2,3)                  (2,4)
            (3,3)                  (3,4)


public class Solution {
    public int getMoneyAmount(int n) {
       int[][] dp = new int[n+1][n+1];
       for(int j = 2; j <= n; j++){
           for(int i = j-1; i > 0; i--){
               dp[i][j] = Integer.MAX_VALUE;
               for(int k = i; k <= j; k++){
                   dp[i][j] = Math.min(dp[i][j],k + Math.max(k-1>=i ?dp[i][k-1]:0, k+1 <= j ?dp[k+1][j]:0));
               }
           }
       }
       return dp[1][n];
    }
}
Share