#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_MATRIX_CHAIN_MULTIPLICATION_COST
#define CA_UWATERLOO_ALUMNI_DWHARDER_MATRIX_CHAIN_MULTIPLICATION_COST

#include <cassert>
#include <climits>

// Author:  Douglas Wilhelm Harder
// Copyright (c) 2009 by Douglas Wilhelm Harder.  All rights reserved.

/*
 * In multiplying m matrices of sizes n  x n , n  x n , ..., n     x n
 *                                     0    1   1    2        m - 1   m
 * we attempt to find the optimal order of multiplication of the matrices.
 *
 * The dimensions of matrix M  are stored in dim[i] and dim[i + 1]
 *                           i
 */

namespace Matrix_chain_multiplications {
	int cost( int *dims, int m ) {
		int table[m][m];

		// The diagonal entries are 0:  there is no prior cost for calculating
		// M  for i = 0, ..., m.
		//  i

		for ( int i = 0; i < m; ++i ) {
			table[i][i] = 0;
		}

		// The off-diagonal entries are straight-forward to calculate:
		//  M  x M      costs n  x n      x n     .
		//   i    i + 1        i    i + 1    i + 2

		for ( int i = 0; i < m - 1; ++i ) {
			table[i][i + 1] = dims[i]*dims[i + 1]*dims[i + 2];
		}

		for ( int k = 2; k < m; ++k ) {
			for ( int i = 0; i < m - k; ++i ) {
				int j = i + k;

				// Calculate the optimal order for M  x ... x M 
				//                                  i          j

				// Set the entry to the largest possible integer
				table[i][j] = INT_MAX;

				for ( int v = i; v < j; ++v ) {
					// Take the minimum of the current value stored
					// in table[i][j] and cost of multiplying:
					//     (M  x ... x M  ) x (M     x ... x M )
					//       i          v       v + 1         j
					// where:
					//    the optimal cost for the first is stored in table[i][v],
					//    the optimal cost for the second is stored in table[v + 1][j], and
					//    the dimensions are dims[i], dims[v + 1], and dims[j + 1].
					//
					// Recall that the dimensions of M  are stored in dims[i] and dims[i + 1]
					//                                i

					table[i][j] = min(
						table[i][j],
						table[i][v] + table[v + 1][j] +
							dims[i]*dims[v + 1]*dims[j + 1]
					);
				}
			}
		}

		// The smallest entry is found in the top-right corner of the matrix
		return table[0][m - 1];
	}
}

#endif