class Solution {
public:
    int dp[201][201];
    int getMoneyAmount(int n) {
        memset(dp,-1,sizeof(dp));
        return dfs(1,n);
    }
    
    int dfs(int l,int r){
        if(l>r)return 0;
        if(l==r){
            return 0;
        }
        if(dp[l][r]!=-1)return dp[l][r];
        int res=INT_MAX;
        
        for(int i=l;i<=r;i++){
            res=min(res,i+max(dfs(l,i-1),dfs(i+1,r)));
        }
        dp[l][r]=res;
        return res;
    }
};