11049 행렬곱셈순서

알고리즘(DP)

1. 연속된 원소를 크게 이등분하여 계산할 수 있음 ex) (start ~ i, i+1~end)
2. dp(start, end)는 start에서 end까지의 범위를 계산할 때 최소비용.
3. 현재 비용은, matrixt[start][0]*matrix[i][1]*matrix[end][1] 로 계산할 수 있음.
4. start == end 일때 비용은 0

코드

#include <iostream>
#define MAX_MATRIX 501
 
using namespace std;
 
int numOfMatrix, matrix[MAX_MATRIX][2], DP[MAX_MATRIX][MAX_MATRIX];
 
int getMinCalulate(int start, int end);
long long min(long long a, int b) {
	return a < b ? a : b;
}
 
int main() {
	cin >> numOfMatrix;
 
	for (int i = 0; i < numOfMatrix; i++)
		cin >> matrix[i][0] >> matrix[i][1];
 
	cout << getMinCalulate(0, numOfMatrix - 1);
}
 
int getMinCalulate(int start, int end) {
	if (start == end)
		return 0;
	if (DP[start][end] != 0)
		return DP[start][end];
 
	long long result = 3000000000;
	for (int i = start; i < end; i++) {
		result = min(result, getMinCalulate(start, i) + getMinCalulate(i + 1, end) + (matrix[start][0]*matrix[i][1]*matrix[end][1]));
 
	}
 
	return DP[start][end] = result;
}