C++ DP solution

  • 1

    dp[i][j] refers to the answer of elements[i+1,j+1]

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

  • 0

    Hello, I have some questions about your code.
    When you express d[i][j], you seemed to use d[i][j] itself to solve d[i][j]...I can't quite follow this.

    Besides, I think dp[k+1][j]+k+1 <= dp[i][j] should always be true when k==i. So why you expressed like dp[i][j] = min(dp[i][j],dp[k+1][j]+k+1) ??

    Thank you so much for your answer! :)

  • 0

    @NoelleSun dp[k+1][j]+k+1 <= dp[i][j] is right,you can improve it.Thank you.

  • 0

    I understand now! Thank you~

Log in to reply

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