minimum multiplication metrix

Dynamic Programing

행렬의 곱을 하는데 최소의 연산수를 구한다.

SOL)
Ai = Pi-1 *Pi 형태이다.
   (left) (right)

m[i][j] = 행렬 Ai * Ai+1 * ... * Aj 를 계산하는데 드는 최소 연산 수
이것은 m[i][j] = min(m[i][k] + m[k+1][j] + Pi-1*Pk*Pj) (단, i <= k <= j-1) 이다.



[-] Collapse

#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF = (1 << 30);

struct matrix{
    int left;
    int right;
}A[100];

int num;
int m[100][100];

int minMult(int i, int j){
    if (m[i][j] != -1) return m[i][j];
    else if (i == j) return m[i][j] = 0;
    else if (i + 1 == j) return m[i][j] = A[i].left * A[i].right * A[j].right;
    else{
        m[i][j] = INF;
        for (int idx = i; idx < j - 1; idx++)
            m[i][j] = min(m[i][j], minMult(i, idx) + minMult(idx + 1, j) + A[i].left*A[idx].right*A[j].right);
    }
    return m[i][j];
}

int main(){
    freopen("input.txt", "r", stdin);
    memset(m, -1, sizeof(m));
    scanf("%d", &num);
    for (int i = 0; i < num; i++)
        scanf("%d%d", &A[i].left, &A[i].right);

    printf("%d\n", minMult(0, num - 1));

}