# 40ms c++ code, and the original recursive solution.

• The 40ms solution is:

``````int getMoneyAmount(int n) {
// idea: an array a[n][n], where a[i][j] denotes the minimum cost to guess correctly for numbers [i, j]
// array lenth 1 -> 0; lenth 2 -> select smaller one; lenth 3 -> select middle;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0x7fffffff));
for (int i = 1; i <= n; i++)dp[i][i] = 0;
for (int i = 1; i <= n - 1; i++)dp[i][i + 1] = i;
for (int i = 1; i <= n - 2; i++)dp[i][i + 2] = i + 1;

// from lenth 3, fill the array out;
for (int nn = 3; nn <= n; nn++)
for (int m = 1; m <= n - nn; m++){
int mini = 0x7fffffff;
for (int i = m + 2; i < m + nn; i++){
int l = dp[m][i - 1];
int r = dp[i + 1][m + nn];
mini = min(mini, max(l, r) + i);
}
dp[m][m + nn] = mini;
}
return dp[1][n];
}
``````

The recursive solution. Not surprisingly that the recursive will timeout, but it is a good start point.

``````int getMoneyAmount_br(int m, int n){ // minimum cost for a correct guess [m, n]
if (m == n)
return 0;
if (n - m < 3)
return (m + n) / 2;

int mini = 0x7fffffff;
for (int i = m + 2; i < n; i++){

int l = getMoneyAmount_br(m, i - 1);
int r = getMoneyAmount_br(i + 1, n);
mini = min(mini, max(l, r) + i);
}

return mini;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.