c++ DP solution


  • 1
    H

    The idea is simple: If I choose x from 1 to n, the cost will be: x + max{dp[1][x-1], dp[x+1][n]}.

    class Solution {
    public:
        int helper(vector<vector<int>>& dp, int start, int end){
            if(start >= end) return 0;
            if(dp[start][end] > 0) return dp[start][end];
            int ans = INT_MAX;
            for(int i = start; i <= end; i ++)
                ans = min(ans, i+max(helper(dp, start, i-1), helper(dp, i+1, end)));
            dp[start][end] = ans;
            return ans;
        }
        
        int getMoneyAmount(int n) {
            vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
            return helper(dp, 1, n);
        }
    };
    

Log in to reply
 

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