c++ more simple DP solution


  • 5
    X
        int getMoneyAmount(int n) {
            vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
            for (int i = 1; i <= n; ++i){
                for (int j = i - 1; j >= 1; --j){
                    int min_value = INT_MAX;
                    for (int k = j; k <= i; ++k){
                        int tmp = k + max(dp[j][k - 1], dp[k + 1][i]);
                        min_value = min(min_value, tmp);
                    }
                    dp[j][i] = min_value;
                }
            }
            return dp[1][n];
        }
    

  • 3
    A

    Thanks for your solution sharing!

    Just add a little explanation for the min/max stuff, in case someone else might need:

    We are using two rules to solve this problem:

    Rule 1 (max) : For a subproblem with multiple choices, pick the minimum-cost one;
    Rule 2 (min) : For a specific guess, go to the worst branch of the two (either higher/lower <-> right/left)


Log in to reply
 

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