375. Guess Number Higher or Lower II

做题历程：

1. 本题是第一次做，耗时超过1小时，没有解出

本题难度不简单，有点涉及博弈论，我也不太懂。。。本题算是Minimax，时间有限，就没怎么看，最近解算法题还是主要是针对题，等面完Google之后，要开始根据不会的算法进行强化。。

大体思路：

1. 核心代码是这一行，理解了这行就理解了算法： ret = min(ret, i + max(solve(dp, left, i - 1), solve(dp, i + 1, right)));
   1. dp是一个二维数组，dp[i][j]指的是在i...j范围内猜的消耗
   2. max是指猜的人无法决定数在左边或右边，所以，按最差情况选大的
   3. min是指尽管我们不能确定数在哪边，但是我们可以选一个最优解，先猜k，这个过程需要思考一下，我想了好久才想明白
2. 然后注意要在recursive的过程中记住dp[i][j]的值，否则就太耗时。。就会TLE

详细代码如下：

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        return solve(dp, 1, n);
    }
private:
    int solve(vector<vector<int>>& dp, int left, int right) {
        if (left >= right) {
            return 0;
        }
        if (dp[left][right]) {
            return dp[left][right];
        }
        int ret = INT_MAX;
        for (int i = left; i <= right; ++i) {

        }
        dp[left][right] = ret;
        return ret;
    }
};