11049

DP의 예시로 알고리즘 책에서 자주 나오는 유형

DP는 배열의 인덱스 값을 얼마나 유용하게 잘 사용하느냐에 달려있는 것 같다.

dp[FROM][TO] : FROM부터 TO까지의 행렬들을 곱할 때의 값

위 값을 통해서 지속적으로 업데이트 해나가면 문제를 풀 수 있다.

 
#include<cstdio>

#define MAXN 500

int dp[MAXN][MAXN];

int data[MAXN][2];

int main() {
	int N;
	int i, j, len;

	freopen("input.txt", "r", stdin);
	scanf("%d", &N);

	for (i = 0; i < N; i++)
		scanf("%d%d", &data[i][0], &data[i][1]);

	for (len = 1; len < N; len++) {
		for (i = 0; i + len < N; i++) {
			for (j = i; j < i+len; j++) {
				if (dp[i][i + len] == 0 ||
					dp[i][i + len] > dp[i][j] + dp[j + 1][i + len] + data[i][0] * data[j + 1][0] * data[i + len][1])
					dp[i][i + len] = dp[i][j] + dp[j + 1][i + len] + data[i][0] * data[j + 1][0] * data[i + len][1];
			}
		}
	}

	printf("%d\n", dp[0][N - 1]);

	return 0;

}