C++ O(N^3) dynamic programming solution


  • 0
    G
    class Solution {
    public:
        int getMoneyAmount(int n) {
            vector<vector<int> > dp(n + 1,vector<int> (n + 1,0));
            
            for(int i = 2; i <= n; ++i){
                for(int j = i - 1; j > 0; j--){
                    if(j == i - 1){
                        dp[j][i] = j;
                    }
                    else{
                        int minVal = INT_MAX;
                        for(int k = j + 1; k < i; ++k){
                            minVal = min(minVal,max(dp[j][k - 1],dp[k + 1][i]) + k);
                        }
                        
                        dp[j][i] = minVal;
                    }
                 }
             }        
            
            return dp[1][n];
        }
        
    };
    

Log in to reply
 

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