int getMoneyAmount(int n) {
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
for (int i = 1; i <= n; ++i){
for (int j = i  1; j >= 1; j){
int min_value = INT_MAX;
for (int k = j; k <= i; ++k){
int tmp = k + max(dp[j][k  1], dp[k + 1][i]);
min_value = min(min_value, tmp);
}
dp[j][i] = min_value;
}
}
return dp[1][n];
}
c++ more simple DP solution


Thanks for your solution sharing!
Just add a little explanation for the min/max stuff, in case someone else might need:
We are using two rules to solve this problem:
Rule 1 (max) : For a subproblem with multiple choices, pick the minimumcost one;
Rule 2 (min) : For a specific guess, go to the worst branch of the two (either higher/lower <> right/left)