Matrix Chain Multiplication Dynamic Programming Implementation with trace

mat-chain-mult-dp-trace.cpp

#include <algorithm>
#include <iostream>
#include <vector>
#include <climits>
#include <string>

using namespace std;

vector<int> rc;
vector< vector<int> > DP, splits;

string mult(int i, int j)
{
	if (i == j) {
		return to_string(i); // Basis
	} else {
		int k = splits[i][j];
		string X = mult(i, k);
		string Y = mult(k + 1, j);
		cout << "multiply " << X << " and " << Y << endl;
		return "(" + X + "*" + Y + ")";
	}
}

int main()
{
	int c; cin >> c;
	int n = c - 1;
	rc = vector<int>(c + 1, -1);
	DP = splits = vector< vector<int> >(c, vector<int>(c, 0));
	int x;

	// for every matrix i, rc[i] is row and rc[i+1] is column
	for (int i = 1; i <= c; i++) {
		cin >> x;
		rc[i] = x;
	}

	for (int w = n; w > 0; w--) {
		int p = n - w;
		for (int j = n; j > p; j--) {
			int i = j - p - 1;
			DP[i][j] = INT_MAX;
			for (int k = i; k < j; k++) {
				int ops = DP[i][k] + DP[k + 1][j] + rc[i] * rc[k + 1] * rc[j + 1];
				if (ops < DP[i][j]) {
					DP[i][j] = ops;
					splits[i][j] = k;
				}
			}
		}
	}

	cout << mult(1, n);
}