class Solution {
public:
    int getMoneyAmount(int n) {
       vector<vector<int>> dp(n + 2,vector<int>(n + 2));

       for(int l = n; l >= 1; l--){
           for(int r = 1; r <= n; r++){
                int &memo = dp[l][r];
                if (l >= r){
                    memo = 0;
                }else {
                    int ans = INT_MAX;

                    for(int i = l; i <= r; i++){
                        ans = min(ans,i + max(dp[i + 1][r],dp[l] [i - 1]));
                    }

                    memo = ans;
                }
           }
       }
       return dp[1][n];
    }
};