LeetCode-375-GuessNumberHigherorLowerII

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个数里面，我们任意猜一个数(设为i)，保证获胜所花的钱应该为 i + max(w(1 ,i-1), w(i+1 ,n))，这里w(x,y)表示猜范围在(x,y)的数保证能赢应花的钱，则我们依次遍历 1-n作为猜的数，求出其中的最小值即为答案。

时间复杂度O(n^2)，空间复杂度O(n^2)

class Solution {
public:
    int getMoneyAmount(int n) {
        vector > dp(n+1, vector(n+1, 0));
        if (n <= 1) return 0;
        return cost(dp, 1, n);
    }
    int cost(vector >& dp, int st, int ed) {
        if (st >= ed) return 0;
        if (dp[st][ed]) return dp[st][ed];
        
        int res = INT_MAX;
        for (int i = st; i <= ed; ++i) {
            res = min(res, i + max(cost(dp, st, i-1), cost(dp, i+1, ed)));
        }
        dp[st][ed] = res;
        return res;
    }
};

碎碎念的分析：（懂了的不用看）

设w为所需要付的钱，当n=1时，只有一个数肯定能赢，w=0；当n=2时，我们可能猜的数为1或2，选择猜1，这时正确答案是1时不用花钱，是2时只需要花1，猜2时同理，比较一下这两种情况，我们选择猜1就能保证获胜且花费最小，w=1; 当n=3时，我们选猜2，最多只需花2就能保证获胜，w=2，这几种是帮助理解的初始状态。
当n很大时，我们随便猜一个数m(m