LeetCode375. Guess Number Higher or Lower II（動态規劃）

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];
    }
}