These are chat archives for kennyledet/Algorithm-Implementations

1st
Oct 2016
Saurabh Vyas
@saurabhvyas
Oct 01 2016 09:19
guys I am really stuck on matrix chain multiplication recursive implementation using c++ my code works for only some i's and j's and not all of them
``````
using namespace std;

#include <iostream>
#include <stdio.h>
#include <algorithm>

// this is the most basic recursive version implementation

int minimum =999999999 ;

int param1 ;
int param2 ;
int param3;

int matrix_chain(int p[] , int i , int j) {

// minimum =p[0]*p[1];

if (i == j) {

cout << "m[" << i << "," << j << "] = " << 0 << "\n";
return 0;

}

for (int k=i; k<j; k++)  {

param1= matrix_chain(p,i,k);
param2= matrix_chain(p,k+1,j);
param3 = p[i-1] * p[k]  * p[j];

cout << (param1+param2+param3) << "\n";

//cout << "param3 : " << p[i-1] * p[j-1] << "\n";
//cout << "p[k] : "  << p[k] << "\n";

if ((param1+param2+param3) < minimum) {

minimum = (param1+param2+param3);

cout << "minimum : "  << minimum;

}

cout << "m[" << i << "," << j << "] = " << minimum << "\n";

return minimum;
}

}

int main() {

int p[]={30,35,15,5,10,20,25};

cout << "answer : " << matrix_chain(p,1,4);

// cout << cut_rod(arr,18) ;

// cout << memoized_cut_rod(arr,10);

// cout << bottom_cut_rod(arr,9);

// print_cut_rod_solution(arr,7);

return 0;

}``````