矩阵连乘

递归：

#include<stdio.h>
#define N 6
int m[N][N]; //最小乘法次数
int RecurMatrixChain(int P[],int i,int j) {
    m[i][j]= 100000;
    if(i== j)
        m[i][j]=0;
    else {
        for(int k=i; k<j; k++) {
            int q=RecurMatrixChain(P,i,k)+RecurMatrixChain(P,k+1,j)+P[i]*P[k+1]*P[j+1];
            if(q<m[i][j]) {
                m[i][j]=q;
            }
        }
    }
    return m[i][j];
}
int main() {
    int P[N+1]= {30,35,15,5,10,20,25};
    for(int i=0; i<N; i++)
        m[i][i]=0;
    printf("%d",RecurMatrixChain(P,0,N-1));
    return 0;
}

动态规划：

#include <stdio.h>
#define N 6
int m[6][6];//最优解
void matrix(int p[]) {
    int i;
    int j;
    for(i=2; i<=6; i++)
        for(j=0; j<6-i+1; j++) {
            m[j][j+i-1]=1000000;
            int k;
            for(k=0; k<i-1; k++) {
                if(m[j][j+i-1]>m[j][j+k]+m[j+k+1][j+i-1]+p[j]*p[j+k+1]*p[j+i])
                 {
                    m[j][j+i-1]=m[j][j+k]+m[j+k+1][j+i-1]+p[j]*p[j+k+1]*p[j+i];
                }
            }
        }
}
int main() {
    int p[7]= {30,35,15,5,10,20,25};
    for(int i=0; i<6; i++)
        m[i][i]=0;
    matrix(p);
    printf("%d\n",m[0][5]);
    return 0;
}

备忘录：

#include <stdio.h>
#define N 6
int m[N][N],s[N][N];//最优解
int p[7]= {30,35,15,5,10,20,25};
int lookupChain(int i, int j) {
    if(m[i][j]>0) return m[i][j];
    if(i==j) return 0;
    int u=lookupChain(i+1, j) + p[i-1]*p[i]*p[j];
    s[i][j] = i;
    for(int k=i+1; k<j; k++) {
        int t = lookupChain(i,k) + lookupChain(k+1, j) + p[i-1]*p[k]*p[j];
        if(t<u) {
            u=t;
            s[i][j] = k;
        }
    }
    m[i][j] = u;
    return u;
}
int memoizedmatrixChain(int n) {
    for(int i=1; i<=n; i++)
        for(int j=i; j<=n; j++)
            m[i][j] = 0;
    return lookupChain(1, n);
}
int main() {
    for(int i=0; i<6; i++)
        m[i][i]=0;
    printf("%d\n",memoizedmatrixChain(N));
    return 0;
}