题目来源
给数字n，猜数字1-n，猜错了就给猜错数字的钱，问最多多少钱能保证赢。
我一开始想着用二分来做？后来想想好像不对。
然后看了tags，用DP，但是没想到怎么DP。
看了下讨论区，result_when_pick_x = x + max{DP([i~x-1]), DP([x+1, j])}
代码如下：
class Solution {
public:
int getMoneyAmount(int n) {
vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
return minMoneyToWin(dp, 1, n);
}
int minMoneyToWin(vector<vector<int>> &dp, int start, int end)
{
if (start >= end)
return 0;
if (dp[start][end] != 0)
return dp[start][end];
int res = INT_MAX;
for (int i=start; i<=end; i++) {
int tmp = i + max(minMoneyToWin(dp, start, i-1), minMoneyToWin(dp, i+1, end));
res = min(res, tmp);
}
dp[start][end] = res;
return res;
}
};
