ADLSI : 連鎖行列積

参考：アルゴリズムイントロダクション15章 動的計画法
コード中のコメントはここに書いてあることです.
勘違いしてるかもしれません.

ソースコード

/*
	連鎖行列積問題
	
	演算結果はカッコ付けの順序にはよらないが、計算量（乗算回数）はカッコ付けの順番に依存する
		ｰ>乗算回数を最小にするカッコ付けを決定する
		　
	P(n) : n個の行列に対するカッコ付けの個数

	P(n) = 1 (n = 1)
	P(n) = \sum_{k = 1}^{n - 1} P(k) * P(n - k) (n >= 2)

	Ω(4^n/n^{3/2}) 

	問題の最適解に部分問題の最適解が含まれる
		ｰ>部分問題最適性

	m[i][j] = A_i, A_jの計算に必要なスカラ乗算の最小回数 (A_n : 行列)

	最適解はA_kとA_k+1で分割すると仮定する

	m[i][j] = 0 (i = j)
	m[i][j] = m[i][k] + m[k + 1][j] + p[i].first * p[k].second * p[j].second(i ≠ j)
*/

const int INF = 1 << 29;

int main()
{
	int n;
	scanf("%d", &n);

	int left[100], right[100];
	int m[100][100];

	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			m[i][j] = INF;

	for(int i = 0; i < n; i++)
	{
		scanf("%d%d", left + i, right + i);
		m[i][i] = 0;
	}

	for(int l = 1; l < n; l++)
	{
		for(int i = 0; i < n - l; i++)
		{
			int j = i + l;
			for(int k = i; k < j; k++)
			{
				m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + left[i] * right[k] * right[j]);
			}
		}
	}

	printf("%d\n", m[0][n - 1]);	
}