C++ dp Solution with easy understanding comments


  • 1
    S
    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++){  //len of range [i,i+1,...,i+len-1]
                for(int i = 1; i + len - 1 <= n; i++){ // the start number of the range
                dp[i][i+len-1] = INT_MAX;
                    for(int j = i ; j <= i + len - 1; j++){ // guess which number first
                        dp[i][i+len-1] = min(dp[i][i+len-1], j + max(dp[i][j-1], dp[j+1][i+len-1]));
                    }
                }
                
            }
            return dp[1][n];
        }
    };
    
    

    dp[i][j] indicates how much money we need to guarantee a win when we guess between i and j.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.