(c++)백준 11049번: 행렬 곱셈 순서

www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

[풀이]

재귀 DP로 풀 수 있는 문제였다.

DP[i][j] : i번째 행렬부터 j번째 행렬까지 곱하는데 필요한 곱셈 연산의 최솟값

점화식

DP[i][j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + Matrix[i].r*Matrix[k].c*Matrix[j].c)

 

#include <iostream>
#include <cstring>//memset
#include <algorithm>//min
#include <vector>
using namespace std;

struct M {
	int r, c;
};

int N;
int DP[501][501];
vector<M>v;

int solution(int s,int e) {
	if (s >= e)
		return 0;
	int& res = DP[s][e];
	//이미 구해놨으면
	if (res != -1)
		return res;
	res = 999999999;
	for (int i = s; i <= e; i++) {
		res = min(res, solution(s, i) + solution(i + 1, e) + v[s].r*v[i].c*v[e].c);
	}
	return res;
}

int main() {
	cin >> N;
	int r, c;
	memset(DP, -1, sizeof(DP));
	v.push_back({ 0,0 });
	for (int i = 1; i <= N; i++) {
		cin >> r >> c;
		v.push_back({ r,c });
	}
	cout << solution(1, N) << '\n';
	return 0;
}