看到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);
}
};
