[프로그래머스][level4] 최적의 행렬 곱셈 (C++)

https://programmers.co.kr/learn/courses/30/lessons/12942

코딩테스트 연습 - 최적의 행렬 곱셈

 

 

[난이도] level4
[유형] DP

[풀이]
다이나믹 프로그래밍으로 해결할 수 있씁니다.
DP[i][j] : i~j 구간의 행렬을 계산했을 때의 최솟값.
DP[i][j] = min(DP[l][i]+DP[i+1][r]+matrix[l][0]*matrix[i][1]*matrix[r][1]) (l<=i<r)

 

#include <vector>
#include <cstring>
using namespace std;
vector<vector<int>> matrix;
int dp[201][201];
int sol(int l,int r){
    if(l==r) return 0;
    int& ret = dp[l][r];
    if(ret!=-1) return ret;
    ret = 2e9;
    for(int i=l;i<r;i++) ret=min(ret,sol(l,i)+sol(i+1,r)+matrix[l][0]*matrix[i][1]*matrix[r][1]);
    return ret;
}
int solution(vector<vector<int>> matrix_sizes) {
    matrix=matrix_sizes;
    memset(dp,-1,sizeof(dp));
    return sol(0,matrix.size()-1);
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/최적의_행렬_곱셈.cpp