DP-2:Matrix Chain Multiplication

// public class Solution {
//     public static int help(int[] p,int s,int e){
//     	if(s>=e||s==e-1){
//            return 0;
//         }
//         int min=Integer.MAX_VALUE;
//         for(int k=s+1;k<=e-1;k++)
//         {
//             int count=help(p,s,k)+help(p,k,e)+(p[s]*p[k]*p[e]);
//             if(count<min)
//                 min=count;
//         }
//         return min;
// 	}

// 	public static int mcm(int[] p){
// 		return help(p,0,p.length-1);
// 	}
// }
public class Solution {
    public static int mcm(int[] p){
        int n=p.length;
        int m[][] = new int[n][n]; 
  
        int i, j, k, L, q; 
  
        /* m[i, j] = Minimum number of scalar multiplications needed 
        to compute the matrix A[i]A[i+1]...A[j] = A[i..j] where 
        dimension of A[i] is p[i-1] x p[i] */
  
        // cost is zero when multiplying one matrix. 
        for (i = 1; i < n; i++) 
            m[i][i] = 0; 
  
        // L is chain length. 
        for (L = 2; L < n; L++) { 
            for (i = 1; i < n - L + 1; i++) { 
                j = i + L - 1; 
                if (j == n) 
                    continue; 
                m[i][j] = Integer.MAX_VALUE; 
                for (k = i; k <= j - 1; k++) { 
                    // q = cost/scalar multiplications 
                    q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; 
                    if (q < m[i][j]) 
                        m[i][j] = q; 
                } 
            } 
        } 
  
        return m[1][n - 1]; }
}
//         int dp[][]=new int[p.length][p.length];
//         for(int i=0;i<=p.length;i++){
//             dp[i][i]=0;
//             dp[i][0]=0;
//             for(int j=1;j<p.length;j++){
//                 if(i>j)
//                     dp[i][j]=0;
//                 if(i==j-1)
//                     dp[i][j]=0;
//             }
//         }
//         for(int i=0;i<=p.length;i++){
//             for(int j=0;j<=p.length;j++){
//                 int min=Integer.MAX_VALUE;
//                 if(dp[i][j]==0)
//                     continue;
//                 else{
//                     for(int k=i+1;k<=j-1;k++)
//                     {
//                         int op=dp[i][k]+dp[k][j]+(p[i]*p[k]*p[j]);
//                             if(op<min)
//                                 dp[i][j]=min;
//                     }}
//             }
//         }
//         return dp[0][p.length];
//     }
// }