【动态规划】矩阵链乘法代码-白红宇

【动态规划】矩阵链乘法代码

阅读量：2234 次

发布时间：2019-05-09

本文共 1047 字，大约阅读时间需要 3 分钟。

CLRS 15.2

#include 
   
    #include 
    
     #include 
     
      int m[101][101];int s[101][101];void matrix_chain_order(int p[], int n){    for(int i=1; i<=n; i++)        m[i][i] = 0;    for(int l=2; l<=n; l++)    {        for(int i=1; i<=n-l+1; i++)        {            int j = i + l - 1;            m[i][j] = INT_MAX;            for(int k=i; k<=j-1; k++)            {                int q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];                if(q < m[i][j])                {                    m[i][j] = q;                    s[i][j] = k;                }            }        }    }}void print_optimal_parens(int i, int j){    if(i == j)        printf("A%d", i);    else    {        printf("(");        print_optimal_parens(i, s[i][j]);        print_optimal_parens(s[i][j]+1, j);        printf(")");    }}int main(){    int p[7] = {30, 35, 15, 5, 10, 20, 25};    memset(m, 0, sizeof(int)*101*101);    memset(s, 0, sizeof(int)*101*101);    matrix_chain_order(p, 6);    printf("%d\n", m[1][6]);    print_optimal_parens(1, 6);    return 0;}