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:

1
2
3
4
5
6
7
8
9
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：

试着去选择每一个数作为猜测的答案，然后分为左边和右边分别考虑。
用一个dp记录子问题的结果，dp数组只需要按照对角线填充就可以了。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int getMoneyAmount(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 0;
        }
        int[][] dp = new int[n + 1][n + 1]; // dp[i][j] is [i,j] costs
        // Fill the upper triangle from mid to top right
        // len is the count of numbers in this range
        for (int len = 2; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int temp = Integer.MAX_VALUE;
                for (int pivot = start; pivot <= start + len - 1; pivot++) {
                    temp = Math.min(temp, pivot + Math.max(dp[start][pivot - 1], (pivot == start + len - 1 ? 0 : dp[pivot + 1][start + len - 1])));
                }
                dp[start][start + len - 1] = temp;
            }
        }
        return dp[1][n];      
    }
}