[leetcode]Guess Number Higher or

看到leetcode官微说他们又更新题啦，点开一看，简单dp嘛。
f[L][R]表表示猜[L, R]这个区间里面的数字需要多少花费，如果我猜是k, L<=k<=R
考虑比较坏的情况，我猜错了，那么花费就是

max(f[L][k-1], f[k+1][r]) + k

为啥呢，因为你猜错了，然后会告诉你是大了还是小了，大了在[L, k-1]这个区间，小了在[k+1, R]这个区间，考虑最坏情况，选大的。
所以状态转移是

f[L][R] = min{max(f[L][k-1], f[k+1][r]) + k}, L<=k<=R

简单的说就是枚举k，看花费是多少，选一个最小的。

class Solution {
public:

    int dfs(int l, int r, vector<vector<int>>& f) {
        if (l == r) return 0;
        if (l > r) return 0;
        if (f[l][r] != -1) return f[l][r];
        int ans = INT_MAX;
        for (int k = l; k <= r; k++) {
            ans = min(ans, max(dfs(l, k - 1, f), dfs(k + 1, r, f)) + k);
        }
        f[l][r] = ans;
        return ans;
    }

    int getMoneyAmount(int n) {
        vector<vector<int>> f(n + 1, vector<int>(n + 1, -1));
        return dfs(1, n, f);
    }
};