# 375 Guess Number Higher or Lower II

給一正整數n，玩猜數字遊戲，範圍是1-n，每猜一個數字就要花該數字數目的錢，且出題者會提示higher或lower。問最少花多少錢可以猜到範圍內任意指定的數字。

example: n=10，那可能指定的數字就是1~10，假設指定數字為i，以下為每個數字需要的$

i=1,$17
i=2,$18
i=3,$19
i=4,$20
i=5,$21
i=6,$22
i=7,$16
i=8,$18
i=9,$21
i=10,$24

那答案就要輸出16。

Concept 每次猜了一個數字之後，出題者會提示higher或lower，由此得知子題目就是higher那一半或lower那一半的子矩陣要花多少金額才能猜到。 因此可以開一個dp二維矩陣，dp[i][j]表示從數字範圍i~j中猜到答案要花多少金額。

Pseudocode

Main(int n):
dp = new Integer[n+1][n+1]
return getMoneyAmount(1, n)

getMoneyAmount(upper, lower):
corner case check
int maximum = 0
for i = upper to lower//i表示出題者出了哪個數字
    maximum = min(maximum, max(getMoneyAmount(lower half), getMoneyAmount(upper half)) + i)

dp[upper][lower] = maximum
return maximum

Code

class Solution {
    Integer[][] dp;
    public int getMoneyAmount(int n) {
        dp = new Integer[n+1][n+1];
        int result = getMoneyAmount(1, n);

        return result;
    }

    private int getMoneyAmount(int lower, int upper) {
        if (lower >= upper) {
            return 0;
        }
        if (dp[lower][upper] != null) {
            return dp[lower][upper];
        }

        int maximum = Integer.MAX_VALUE;
        for (int i = lower; i <= upper; i++) {
            maximum = Math.min(maximum, Math.max(getMoneyAmount(lower, i-1), getMoneyAmount(i+1, upper)) + i);
        }
        dp[lower][upper] = maximum;

        return maximum;
    }
}