dp：矩陣連乘問題

問題描述：給定n個矩陣：A1,A2,...,An，其中Ai與Ai+1是可乘的，i=1，2，...，n-1。确定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數乘次數最少。輸入資料為矩陣個數和每個矩陣規模，輸出結果為計算矩陣連乘積的計算次序和最少數乘次數。

直接上代碼

#include<stdio.h>
#include<math.h>
#include<iostream>
#include<string.h>
using namespace std;
int p[]={30,35,15,5,10,20,25}; //這是六個矩陣次元，因為有重複的，是以隻有7個
void MatrixChain(int *p,int n,int m[][20],int s[][20])//自底向上的計算m[i][j]和s[i][j]，m[i][j]指從Ai到Aj共需多少次乘法，s[i][j]指每次m[i][j]斷裂的位置k
{
    for(int i=1;i<=n;i++)   //初始化m[i][j]和s[i][j]
        for(int j=1;j<=n;j++)
        m[i][j]=s[i][j]=0;
    for(int r=1;r<=n-1;r++)   //核心步驟，r為步長，因為計算方向是從左上到右下斜着的，并且總的順序是從左到右，
        for(int i=1;i<=n-r;i++)//從上到下的，是以一共有n-1輪，每一輪的步長(指i和j的距離)r，每一輪有n-r趟
        {
            int j=i+r;  //因為每一輪的步長固定都是r，即j-i=r，這裡是友善後面代碼的可讀性，是以定義j=i+r
            m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];//不是為了求k從i到j-1所有情況下m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]的最小值嗎，這裡就先讓k取i咯，友善之後一一打擂台賽
            s[i][j]=i;   //同時讓s[i][j]也為k=i時的取值
            for(int k=i+1;k<j;k++)  //下面的就比較簡單，就是簡單的比大小擂台賽
            {
                if(m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]<m[i][j])//如果有k從i+1到j-1這些情況比最小值還小的就交換
                {
                    m[i][j]=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    s[i][j]=k;
                }
            }
        }
}

void Traceback(int i,int j,int s[][20])//已知s[i][j]，想要輸出最終結果，到底是一個怎麼樣的乘法順序呢？用這個遞歸函數可以解決
{
    if(i==j)  //如果i和j相等還需要輸出嗎，就自己一個沒什麼含義，是以直接return
        return;
    Traceback(i,s[i][j],s);//類似于深度優先周遊一樣，先要打破砂鍋問到底，一定要找出最開始的解，是以不斷壓棧
    Traceback(s[i][j]+1,j,s);//同上
    cout<<"Multiply A"<<i<<","<<s[i][j];//好了，現在可以開始彈棧輸出了
    cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;
}

int main()
{
    int m[20][20],s[20][20];
    MatrixChain(p,6,m,s);
    cout<<"最終政策如下"<<endl;
    Traceback(1,6,s);
    puts("");
    cout<<"最少要進行"<<m[1][6]<<"次乘法"<<endl;
    puts("");
    cout<<"下面是m[i][j]和s[i][j]的輸出！"<<endl;
    for(int i=1;i<=6;i++)
        for(int j=1;j<=6;j++)
        {
            if(j<i)
            {
                cout<<"        ";
                continue;
            }
            printf("%-7d ",m[i][j]);
            if(j==6)
                cout<<endl;
        }
    puts("");
    for(int i=1;i<=6;i++)
        for(int j=1;j<=6;j++)
        {
            if(j<i)
            {
                cout<<"        ";
                continue;
            }
            printf("%-7d ",s[i][j]);
            if(j==6)
                cout<<endl;
        }
}