Matrix-chain multiplication problem

問題文 :
n個の行列の連鎖 が与えられたとき、スカラー乗算の回数が最小になるように積A1A2A3...Anを完全に括弧付ける問題を連鎖行列積問題(matrix-chain multiplication problem)という。

n個の行列について、行列Aiの次元が与えられたとき、積A1A2...Anの計算に最小限必要なスカラー乗算の回数を求めるプログラムを作成せよ。

解法 :
簡単な区間DPの問題で、有名題.
DP[l][r] : l ~ rの行列の乗算回数の最小値とすると,

DP[l][r] = min(DP[l][i] + DP[i + 1][r] 行列A1...Ai とAi+1...Arをかけるコスト)
となる.

AOJ 0145のCardsにとても近い問題である.

コード :

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>

using namespace std;

int r[100], c[100];
int dp[100][100];

int optMat(int left, int right)
{
	if (dp[left][right] >= 0){
		return (dp[left][right]);
	}
	if (left == right){
		return (0);
	}
	
	int res = INT_MAX;
	for (int i = left; i < right; i++){
		res = min(res, optMat(left, i) + optMat(i + 1, right) + r[left] * c[i] * c[right]);
	}
	
	return (dp[left][right] = res);
}

int main()
{
	int N;
	
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++){
		scanf("%d %d", &r[i], &c[i]);
	}
	
	memset(dp, -1, sizeof(dp));
	
	printf("%d\n", optMat(0, N - 1));
	
	return (0);
}