matrix chain multiplication

[surfersss]

  
// See the Cormen book for details of the following algorithm 
#include<stdio.h> 
#include<limits.h> 
  
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n 
int MatrixChainOrder(int p[], int n) 
{ 
  
    /* For simplicity of the program, one extra row and one 
       extra column are allocated in m[][].  0th row and 0th 
       column of m[][] are not used */
    int m[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; 
            m[i][j] = INT_MAX; 
            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 main() 
{ 
    int arr[] = {1, 2, 3, 4}; 
    int size = sizeof(arr)/sizeof(arr[0]); 
  
    printf("Minimum number of multiplications is %d ", 
                       MatrixChainOrder(arr, size)); 
  
    getchar(); 
    return 0; 
} 

im trying to learning matrix chain multiplication using dp, but i find it hard to code it by myself,
especially i dont quite understand the role of i,j,k,L here
even to understand this code i need quite long time like a day ...
and i realize that i cant code it if i dont understand the role of each variable
i know L is for the partition of chain matrix, it can be 2,3,4
but what is role of i,j,k?
and how can i know the loop for i is until n-L+1
and what is role of k?
i know its like filling table but after i made table and trace , i still dont understand
for this part, q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
its hard to come up with this equation p[i-1]*p[k]*p[j];
can someone explain, how to code this problem, and also some problem that require understanding of 3 variable like i ,j ,k in loop,
do you trace and make strategy first?

[jonnin]

i is a loop counter and its role changes depending on which loop you are in.

j is only set in one place: j = i+L-1; and its used as a column index for M. I can't say why as I don't know the algorithm, but do you see in your algorithm a place where the columns are iterated using a formula like this? If your algorithm is presented in [1] is the first in an array, the -1 may be missing in the book text making it something = i+L or something = row+L?

k is also a loop counter, used in P and M both, again -- you would have to look at your algorithm to see where P is being iterated (it appears to be a 1-d vector?)

so basically your strategy needs to be to look at the text/pseudocode/whatever version of the algorithm and understand it, and then back-translate these variables to the algorithm to see how it works.

A great way to see what it is doing is to make a very simple problem, like a small matrix multiply that just gives a single number or 1-d small vector back, and add a bunch of print statements saying what every value in the code is, and then looking at that to see what it did and how it works. That will help, but a combined approach of study the algorithm and then study the code is probably best.

triple nested loops are not something most people can just eyeball and understand. This is going to take some time to fully understand.