share my 10 lines cpp solution using dp


  • 1
    Z
    int getMoneyAmount(int n) {
            int dp[n+1][n+1]={0};
            for(int i=1;i<=n;i++)
                for(int j=i-1;j>=1;j--){
                    dp[j][i]=j+dp[j+1][i];
                    for(int k=j+1;k<i;k++)
                        dp[j][i]=min(dp[j][i],k+max(dp[j][k-1],dp[k+1][i]));
                }
            return dp[1][n];
        }

Log in to reply
 

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