1. ## Recursive Matrix Chain

having trouble implementing the Recursive-Matrix-Chain algorithm found in the Cormen, Leiserson "Intro to Algorithms" books.

this algorithm looks for the minimum number of scalar multiplications needed to compute the product of a series of matrices, NOT the actual product of multiplying the matrices

the results are stored in a two dimensional array M[][]

this is a sample of dynamic programming

here is what I have come up with, and if you run this you can see that not every position is being examined

Any help would be appreciated

Code:
```#include <iostream>
#include <cstdlib>

using namespace std;

const int SIZE = 7;
const int MAX = 99999;

int M[SIZE][SIZE];
int i, k, q, j;
int P[SIZE] = { 25,10,15,5,30,10,15};

int Recursive_Matrix(int i, int j);
void Print_M();

int main()
{

Recursive_Matrix( 1, SIZE-1);
Print_M();

system("PAUSE");
return 0;
}

int Recursive_Matrix(int i, int j)
{
if( i == j )
return 0;
else
{
M[i][j] = MAX;
for(k = i; k <= j-1; k++)
{
q =  Recursive_Matrix(i, k) + Recursive_Matrix( k+1, j) +  ( P[i-1] * P[k] * P[j] );
if( q < M[i][j])
M[i][j] = q;
}
}
return M[i][j];
}

void Print_M()
{
for(int x = 1; x<= SIZE; x++)
{
for(int y = 1; y <= SIZE; y++)
{
cout << M[x][y] << "  ";
}
cout << endl;
}
}```

2. The algorithm looks correct, have you tried the nonrecursive
one? You have to remember
that arrays in the book are 1-based while arrays in
c++ are 0-based.

3. Nick, thanks for checking...

I had no problem implementing the nonrecursive algorithm

just banging my head with this one

maybe someone else will notice something

4. You shouldn't have the global variables at the start.

5. Why do you need a 2-dimensional array to hold the values of q???

Code:
```if( q < M[i][j])
M[i][j] = q;```
it doesn't seem like your incrementing the values of i or j so M[i][j] is always in the same postion.

6. Does this work? Since you have SIZE matrices your going to
have SIZE + 1 dimensions P.

Code:
```#include <iostream>
#include <cstdlib>

using namespace std;

const int SIZE = 7;
const int MAX = 999999;

int M[SIZE][SIZE];

// multiply
// 1x1, 1x2, 2x3, 4x5, 6x7
int P[SIZE + 1] = { 1, 1, 2, 3, 4, 5, 6, 7};

int Recursive_Matrix(int i, int j);
void Print_M();

int main()
{

Recursive_Matrix( 1, SIZE - 1);
Print_M();
return 0;
}

int Recursive_Matrix(int i, int j)
{
int q;

if( i == j )
return 0;
else
{
M[i][j] = MAX;
for(int k = i; k <= j - 1; k++)
{
q =  Recursive_Matrix(i, k);
q += Recursive_Matrix( k+1, j);
q +=  P[i-1] * P[k] * P[j];
if( q < M[i][j])
M[i][j] = q;
}
}
return M[i][j];
}

void Print_M()
{
for(int x = 0; x < SIZE; x++)
{
for(int y = 0; y < SIZE; y++)
{
cout << M[x][y] << "  ";
}
cout << endl;
}
}```

7. // 1x1, 1x2, 2x3, 4x5, 6x7
int P[SIZE + 1] = { 1, 1, 2, 3, 4, 5, 6, 7};

should be
// 1x1, 1x2, 2x3, 3x4, 4x5, 5x6, 6x7

8. I did something wrong ...

9. Nick, you don't have to make size+1

it works with your changing the structure of the statement that makes the recursive calls

i get the correct reults now, THANKS!

The parenthization is wrong, but i can fix that!

Code:
```Results:

Recursive
0  0  0  0  0  0  0
0  0  15750  7875  9375  11875  15125
0  0  0  2625  4375  7125  10500
0  0  0  0  750  2500  5375
0  0  0  0  0  1000  3500
0  0  0  0  0  0  5000
0  0  0  0  0  0  0

0  1  2  3  4  5
0  0  2  3  4  5
0  0  0  3  4  5
0  0  0  0  4  5
0  0  0  0  0  5

(((((A1A2)A3)A4)A5)A6)

Non-Recursive

0  15750  7875  9375  11875  15125
0  0  2625  4375  7125  10500
0  0  0  750  2500  5375
0  0  0  0  1000  3500
0  0  0  0  0  5000

0  1  1  3  3  3
0  0  2  3  3  3
0  0  0  3  3  3
0  0  0  0  4  5
0  0  0  0  0  5

((A1(A2A3))((A4A5)A6))

********************CODE

#include <iostream>
#include <cstdlib>

using namespace std;

const int SIZE = 7;
const int MAX = 999999;

int M[SIZE][SIZE];
int S[SIZE][SIZE];

// multiply
// 1x1, 1x2, 2x3, 4x5, 6x7
//int P[SIZE + 1] = { 1, 1, 2, 3, 4, 5, 6, 7};
int P[SIZE] = {30,35,15,5,10,20,25};

int Recursive_Matrix(int i, int j);
void Print_Optimal_Parens(int S[][SIZE], int i, int j);
void Print_M();
void Print_S();

int main()
{

Recursive_Matrix( 1, SIZE - 1);
Print_M();
cout << endl << endl;
Print_S();
cout << endl << endl;
Print_Optimal_Parens( S, 1, SIZE-1);
cout << endl << endl;
system("PAUSE");
return 0;
}

int Recursive_Matrix(int i, int j)
{
int q;

if( i == j )
return 0;
else
{
M[i][j] = MAX;
for(int k = i; k <= j - 1; k++)
{
q =  Recursive_Matrix(i, k);
q += Recursive_Matrix( k+1, j);
q +=  P[i-1] * P[k] * P[j];
if( q < M[i][j])
M[i][j] = q;
S[i][j] = k;

}
}
return M[i][j];
}

void Print_M()
{
for(int x = 0; x < SIZE; x++)
{
for(int y = 0; y < SIZE; y++)
{
cout << M[x][y] << "  ";
}
cout << endl;
}
}

void Print_Optimal_Parens(int S[][SIZE], int i, int j)
{
if(i == j)
cout << "A" << i;
else
{
cout << "(";
Print_Optimal_Parens(S, i, S[i][j]);
Print_Optimal_Parens(S, (S[i][j])+1, j);
cout << ")";
}
}

void Print_S()
{
for(int x = 1; x<= SIZE-2; x++)
{
for(int y = 1; y <= SIZE-1; y++)
{
cout << S[x][y] << "  ";
}
cout << endl;
}
}```

10. This version works. I thought you had SIZE for being
the number of matrices.

Code:
```#include <iomanip>
#include <iostream>
#include <cstdlib>

using namespace std;

const int SIZE = 6;
const int MAX = 999999;

int M[SIZE][SIZE];

// multiply
// 1x1, 1x2, 2x3, 3x4, 4x5, 5x6, 6x7
int P[SIZE + 1] = { 30, 35, 15, 5, 10, 20, 25};

int Recursive_Matrix(int i, int j);
void Print_M();

int main()
{

Recursive_Matrix( 0, SIZE - 1);
Print_M();
return 0;
}

int Recursive_Matrix(int i, int j)
{
int q;

if( i == j )
return 0;
else
{
M[i][j] = MAX;
for(int k = i; k <= j - 1; k++)
{
q =  Recursive_Matrix(i, k);
q += Recursive_Matrix( k+1, j);
q +=  P[i] * P[k + 1] * P[j + 1];
if( q < M[i][j])
M[i][j] = q;
}
}
return M[i][j];
}

void Print_M()
{
for(int x = 0; x < SIZE; x++)
{
for(int y = 0; y < SIZE; y++)
{
cout << setw(7) << M[x][y];
}
cout << endl;
}
}```