C++ DP solution


  • 1
    H

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

    class Solution {
    public:
        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);
                        }else{
                            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
    H

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


  • 0

    @huanyingtianhe
    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.