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 501using 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;}