【题目描述】

给定n个矩阵{A1,A2….An}（n<100），其中Ai与Ai+1是可以相乘的，判断这n个矩阵通过加括号的方式相乘，使得相乘的次数最少。

【输入说明】

输入第一行是一个正整数，表示有n个矩阵。之后有n行数字，每行由两个正整数组成，表示第i个矩阵的行数和列数，两个数字之间用一个空格间隔。

【输出说明】

输出只有一个正整数，表示最少的相乘次数

【输入样例】

3

2 3

3 2

2 4

【输出样例】

28

#include <stdio.h>
#define N 20 
void MatrixChain(int p[N], int n, int m[N][N], int s[N][N]) {
    int i, j, t, k;
    int r;             
    for (i = 1; i <= n; i++) {
        m[i][i] = 0;         
    }
    for (r = 2; r <= n; r++) {
        for (i = 1; i <= n - r + 1; i++) {
            j = i + r - 1; 
            m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];  
            s[i][j] = i; 
            for (k = i + 1; k < j; k++) {
                t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (t < m[i][j]) {
                    m[i][j] = t;
                    s[i][j] = k;
                }
            }
        }
    }
}

int main(void) {
    int n, n1, m1, i, j = 2;
    int p[N] = { 0 };           
    int m[N][N] = { 0 };        
    int s[N][N] = { 0 };         
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d %d", &n1, &m1);
        if (i == 1) {
            p[0] = n1;
            p[1] = m1;
        }
        else {
            p[j++] = m1;
        }
    }
    MatrixChain(p, n, m, s);
    printf("%d\n", m[1][n]);
    return 0;
}