问题描述

实现矩阵连乘算法。输入n个矩阵的维度（n+1个数, n>2），输出矩阵连乘的最小数乘次数以及连乘次序，即矩阵加括号的方式，如: (A1((A2A3)A4))。

提交格式：
实现void solve(int n,int p[],int out[])函数。

参数n为矩阵个数，p为关于矩阵维数的n+1个数，矩阵Ai的维数为(p[i-1],p[i]),out[0]为最小数乘次数MOD1000000007，out[i]为输出的连乘次序(i>0)。2<n<=500,2<p[i]<=500。

输出连乘次序时，请将(替换为-1、)替换为-2，矩阵Ai替换为i,输出到out数组中。
请不要printf输出任何内容。

输入样例：

1
n=5,p={10,5,2,8,6,3}

输出样例：

1
out={292,-1,-1,1,2,-2,-1,-1,3,4,-2,5,-2,-2}
核心思路
  1. 最优子结构分析，建立递归关系，得到递归表达式；
  2. 依据其递归式以自底向上的方式进行迭代，得到m矩阵和s矩阵；
  3. 通过s矩阵加括号；
  4. 构造主函数进行调试。
实现要点
  1. 关键在于构造递推表达式，这也是动态规划的难点所在；
  2. 由于数据可能比较大，数据类型选择long long;
  3. 虽然题目是加数字，但和加括号一样，借助通过递归实现。
code
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<stdio.h>
#include <stdlib.h>

long long m[500][500], s[500][500];
long long number;
void traceback(long long i, long long j, int* out);
void solve(int n, int p[], int out[])
{
    for (long long i = 1; i <= n; i++) m[i][i] = 0;
    for (long long r = 1; r <= n - 1; r++)  //r是i和j的间隔宽度
        for (long long i = 1; i <= n - r; i++) //随着间隔宽度r的增长，i递减，直到i为1
        { 
            long long j = i + r;
            m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; // 在i的位置断链,分解为m[i][i]和m[i+1][j]。
            s[i][j] = i;
            for (long long k = i + 1; k < j; k++) // 计算最小的m[i][j]
            { 
                long long 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;
                } //k是i和j之间的最佳断链位置
            }
        }
    out[0] = m[1][n]% 1000000007;
    for (long long i = 1; i <= n; i++)
    {
        out[i] = i;
    }
    number = n;
    traceback(1,n,out);
}

void traceback(long long i, long long j, int* out)
{
    long long k;
    if (i == j) return ;
    else {
        for (k = number; out[k + 1] != i; k--)
        {
            out[k + 1] = out[k];
        }
        out[k+1] = -1;
        number++;
        for (k = number; out[k] != j; k--)
        {
            out[k + 1] = out[k];
        }
        out[k + 1] = -2;
        number++;
        traceback(i, s[i][j], out);
        traceback(s[i][j] + 1, j, out);
    }
}

int main()
{
    int n=5;
    int p[6] = { 10,5,2,8,6,3 };
    int out[1500] = {0};
    solve(n, p, out);
    printf("out=");
    for (int i = 0; i <= number; i++)
    {
        printf("%d,", out[i]);
    }
    system("pause");
    return 0;
}