Description

Submission

class Solution {
public:
    int getMoneyAmount(int n) {

        vector<vector<int>> dp(n + 2, vector<int> (n + 2, 0));

        for(int len = 2; len <= n; ++len) {
            // [i, i + len - 1]
            for(int i = 1; i <= n - len + 1; ++i) {
                int j = i + len - 1; 
                dp[i][j] = INT_MAX;
                for(int k = i; k <= j; ++k) {
                    dp[i][j] = min(dp[i][j], max(dp[i][k-1], dp[k+1][j]) + k);
                }
            }
        }

        return dp[1][n];
    }
};

// dp[i][j]: guarantee a win guessing in the range [i, j]