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.

dp[i][j]代表數字i到j之間猜中任意一個數字最少需要花的錢。 每在一個區間[i...j]內選一個數字k，就能把區間分成兩段，然後取當前這個選擇的數字k的成本加上左右兩個區間較大的成本為local max，因為要選擇一個最壞的狀況才能包含所有可能的情形。如果i和j是相鄰的兩個數，這種情況類似我們有兩個數字1和2，我們一定會猜1，因為如果猜錯，那我們的成本就是1，然後馬上知道答案是2。如果猜對，那答案就是1。所以相鄰兩個數的情況我們會選擇較小的數當作cost。

// Bottom-Up Dynamic Programming
int getMoneyAmount(int n) { // time: O(n^3); space: O(n^2)
    vector<vector<int> > dp(n + 1, vector<int>(n + 1, 0));
    for (int i = 2; i <= n; ++i) {
        for (int j = i - 1; j > 0; --j) {
            int global_min = INT_MAX;
            for (int k = j + 1; k < i; ++k) {
                int local_max = k + max(dp[j][k - 1], dp[k + 1][i]);
                global_min = min(global_min, local_max);
            }
            dp[j][i] = j + 1 == i ? j : global_min; // case: [1, 2], we can choose 1 because it costs less
        }
    }
    return dp[1][n];
}

// Top-Down Dynamic Programming with Memoization
int getMoneyAmount(int n) { // time: O(n^3); space: O(n^2)
    vector<vector<int> > memo(n + 1, vector<int>(n + 1, 0));
    return helper(1, n, memo);
}
int helper(int start, int end, vector<vector<int> >& memo) {
    if (start >= end) return 0;
    if (memo[start][end] > 0) return memo[start][end];
    int global_min = INT_MAX;
    for (int k = start; k <= end; ++k) {
        int local_max = k + max(helper(start, k - 1, memo), helper(k + 1, end, memo));
        global_min = min(global_min, local_max);
    }
    return memo[start][end] = global_min;
}