```
int getMoneyAmount(int n) {
int dp[n+1][n+1]={0};
for(int i=1;i<=n;i++)
for(int j=i-1;j>=1;j--){
dp[j][i]=j+dp[j+1][i];
for(int k=j+1;k<i;k++)
dp[j][i]=min(dp[j][i],k+max(dp[j][k-1],dp[k+1][i]));
}
return dp[1][n];
}
```