本文共 1904 字，大约阅读时间需要 6 分钟。

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.

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

猜数字，每当你猜错，就要付出相同猜的数字的钱。你猜错了8，那么就要付8元。那么你至少需要多少钱才能保证你一定能猜对。

动态规划，dp[i][j] 表示i-j的数字你至少需要多少钱。

1. 初始化，当i + 1 = j时，那么肯定是猜i用的钱少。

2. 动态方程dp[i][j] = k + max(dp[i][k - 1], dp[k+1][j]).  k ∈[i + 1, j - 1].  k表示，如果你猜首先猜k，那么你保证你猜对，就要取两边较大的结果。

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