c++ DP solution

  • 1

    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 {
        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.