375. Guess Number Higher or Lower II

We are playing the Guessing Game. The game will work as follows:

1. I pick a number between 1 and n.
2. You guess a number.
3. If you guess the right number, you win the game.
4. If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
5. Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.

Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.

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