用动态规划求解矩阵乘法链问题

coding>C++
1.2k 词

题目描述

设矩阵A为$100×1$的矩阵，B为$1×100$矩阵，C为$100×1$的矩阵，则计算$A×B$的时间耗费为$10000$（由$100×1×100$得到），得到的结果D为$100×100$矩阵，再与C相乘所需的时间耗费为$1000000$，因此计算$(A×B)×C$的总时间$1010000$。$B×C$的时间耗费为$10000$，得到的中间矩阵为$1×1$矩阵，再与Ａ相乘的时间耗费为$100$，因而计算$A×(B×C)$的时间耗费只有$10100$。从上面的分析可以看的出不同的乘法顺序所耗费的时间是不同，甚至是相差很大的。现有一矩阵链$M1×M2×M3×M4×M5×M6………$，试问如何选择计算顺序才能使所耗费的时间最少。

输入

矩阵乘法链长度为N的问题其输入数据由$N＋1$行组成，第一行为矩阵乘法链的长度，即矩阵的个数。剩下的N行为N个矩阵的行列信息。每行的第一个元素是矩阵行数，第二个元素是矩阵的列数，元素之间以空格隔开。

输出

输出计算这个矩阵乘法链的最少耗费时间。

样例输入

1
2
3
4
5
6
7
6
30 35
35 15
15 5
5 10
10 20 
20 25

样例输出

1
15125

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<vector>
#include<algorithm>
const int Max = 1 << 30;
using namespace std;
int n;
vector<int> dim;
int m[1010][1010];
int main() {
    cin >> n;
    int p1, p2;
    scanf("%d%d", &p1, &p2);
    dim.push_back(p1);
    dim.push_back(p2);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &p1, &p2);
        dim.push_back(p2);
    }
    for (int i = 1; i <= n; i++)
        m[i][i] = 0;
    for (int c = 2; c <= n; c++)
        for (int i = 1; i <= n - c + 1; i++){
            int j = i + c - 1; 
            m[i][j] = Max; 
            for (int k = i; k <= j - 1; k++) { 
                int q = (m[i][k] + m[k + 1][j] + dim[i - 1] * dim[k] * dim[j]);
                if (q < m[i][j])
                    m[i][j] = q;
            }
        }
    cout << m[1][n] << endl;
    return 0;
}