矩阵链乘法

递归算法：

#include<string>
#include<cstring>
#include<iostream>
using namespace std;

int n;
int p[100];
int m[100][100];
int s[100][100];
int dp(int i,int j){
    if(i==j)               /*如果只有一个矩阵就直接返回*/
        return m[i][j];
    m[i][j]=999999999;     /*将m[i][j]设为无穷大*/
    s[i][j]=i;
    for(int k=i;k<j;k++){  /*将i到j个矩阵分为i到k和k+1到j个矩阵*/
        int q=dp(i,k)+dp(k+1,j)+p[i-1]*p[k]*p[j]; 
        if(q<m[i][j]){      /*如果有更小的方案更新*/
            m[i][j]=q;
            s[i][j]=k;
        }
    }
    return m[i][j];         
}
int main(){
    while(cin>>n){
        for(int i=0;i<=n;i++){  /*输入矩阵链*/
            cin>>p[i];
        }
        memset(m,0,sizeof(m));    /*初始化*/
        dp(1,n);                    /*查找目标1到n个矩阵链乘*/
        cout<<m[1][n]<<" "<<s[1][n]<<endl;
    }
    return 0;
}

迭代算法：

#include<string>
#include<cstring>
#include<iostream>
using namespace std;

int main(){
    int n;
    int p[100];
    while(cin>>n){
        for(int i=0;i<=n;i++){   /*输入矩阵链*/
            cin>>p[i];
        }
        int m[100][100];            /*存最少操作*/
        int s[100][100];            /*存最后一次操作的位置*/
        memset(m,0,sizeof(m));      /*初始化m数组*/
        for(int i=0;i<=n;i++){                                  
            for(int j=i;j<=n;j++){
                s[i][j]=i;          /*初始化s数组*/
            }
        }
        for(int r=2;r<=n;r++){          /*操作的矩阵数*/
            for(int i=1;i<=n-r+1;i++){
                int j=i+r-1;
                m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];   /*将第一个矩阵与其它矩阵分开*/
                s[i][j]=i+1;
                for(int k=i+1;k<j;k++){                 /*将前K个矩阵与后面的矩阵分开*/
                    int 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;
                    }
                }
            }
        }
        cout<<m[1][n]<<" "<<s[1][n]<<endl;
    }
    return 0;
}

分析

递归算法：规模为n的问题，有n个递归，每个递归又有相应矩阵个数个递归，故T(n)=T(1)+T(n-1)+1+T(2)+T(n-2)+1......+T(n-1)+T(1)+1=n-1+2*(T(1)+T(2)+......T(n-1))=O(n^2)。
迭代算法：规模为n的问题，用迭代算法，即用已知值计算新值，需要将问题划分成两个一组、三个一组......n个一组的子问题，故
T(n)=T(n-1)+T(n-2)+T(n-3)......+T(1)=O(n^2).