一.動態(tài)規(guī)劃（DP）的定義：

求解決策過程（decision process）最優(yōu)化的數(shù)學方法。

將多階段決策過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解。

二.動態(tài)規(guī)劃的基本思想：

與分治法類似，將待求解問題分解成若干個子問題。

但是經(jīng)分解得到的子問題往往不是相互獨立的。

如果使用分治法求解問題，有些子問題被重復計算了多次。

而“如何減少子問題的重復計算”是動態(tài)規(guī)劃算法的關鍵思想。

問題：如何減少子問題的重復計算呢？

解決方案：保存已解決的子問題的答案，在需要的時候找出已經(jīng)求得的答案。

三.動態(tài)規(guī)劃的基本步驟

1.找出最優(yōu)解的性質，并刻劃其結構特征。即：尋找最優(yōu)解的子問題結構。

2.遞歸地定義最優(yōu)解。即：根據(jù)子問題的結構建立問題的遞歸解式，求解最優(yōu)值。

3.以自底向上的方式計算出最優(yōu)值。

4.根據(jù)計算最優(yōu)值時得到的信息，構造最優(yōu)解。

四.例題分析——多個矩陣連乘模塊設計

問題描述：

實現(xiàn)多個矩陣連乘功能

關鍵問題計算：

給定n個矩陣{}，其中與是可乘的，考察這n個矩陣的連乘積

由于矩陣乘法滿足結合律，所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。

若一個矩陣連乘積的計算次序完全確定，也就是說該矩陣已完全加括號，則可以依此次序反復調(diào)用3個矩陣相乘的標準算法計算出矩陣連乘積。

完全加括號的矩陣連乘積：

設有四個矩陣 A，B，C，D 維數(shù)分別為：

50*10；10*40；40*30；30*5

則總共有五種完全加括號的方式：

1）

（A（（BC）D））

2）

（A（B（CD）））

3）

（（AB）（CD））

4）

（（（AB）C）D）

5）

（（A（BC））D）

對于兩個矩陣A(p*q)*B(q*r)（標準乘法計算）：

void matrixMultiply(int *a,int *b,int *c,int ra,int ca,int rb,int cb){
    if(ca!=rb){
        cout<<"矩陣不可乘！"<<endl;
    }
    else{
        int i,j,k,n,sum=0;
        for(i=0;i<ra;i++){
            for(j=0;j<cb;j++){
                for(k=0;k<ca;k++){
                    sum+=a[i*ca+k]*b[k*cb+j];
                }
                c[i*ra+j]=sum;
                sum=0;
            }
        }
        
    }
}

需要進行p*q*r次乘法計算！

矩陣連乘問題轉化為：

確定矩陣連乘的計算次序，使得按照該次序計算矩陣連乘需要的數(shù)乘次數(shù)最少。

1.窮舉法求解思路：

????????列舉出所有可能的計算次序，并計算出每一種次序相應需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。

算法復雜度分析：

對于n個矩陣的連乘積，設其不同的計算次序為P（n）

由于每種加括號方式都可以分解為兩個子矩陣的加括號的問題

2.動態(tài)規(guī)劃求解：

最優(yōu)解結構分析：

將矩陣連乘積簡記為：A[i:j]，這里i<=j。

設這個計算次序在和之間將矩陣斷開，i<=k<j，則其相應的完全加括號的方式為：

（）()

總計算量=A[i:k]的計算量加上A[k+1:j]的計算量，再加上A[i:k]和A[k+1:j]相乘的計算量。

特征：計算A[i:j]的最優(yōu)次序所包含的計算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優(yōu)的。

最優(yōu)子結構性質：最優(yōu)解包含其子問題的最優(yōu)解。

建立遞歸關系：(m[i,j]表示最小連乘次數(shù)）

當i=j時，A[i:j]=,m[i,j]=0

當i<j時，m[i,j]={m[i,k]+m[k+1,j]+}

則有：

(k的位置只有j-i種可能）?

注：由于矩陣乘法中的列數(shù)和的行數(shù)相等，則可以只用列數(shù)來化簡表達式，這里的均表示第i-1，k，j個矩陣的列數(shù)。n個矩陣的信息，只需要一個長度為n+1的數(shù)組來表示即可。

對于m[i][j]數(shù)組，只需要填入上三角中的元素即可（因為i<=j）。

五.代碼實現(xiàn)文章來源地址http://www.zghlxwxcb.cn/news/detail-772711.html

#include <iostream>
using namespace std;
int BestValue(int row[],int col[], int n);
int main(int argc, const char * argv[]) {
    int row[]={3,4,6};
    int col[]={4,6,11};
    cout<<BestValue(row, col, 3);
    return 0;
}
int BestValue(int row[],int col[], int n){
    if(n<=0){
        cout<<"error";
        return 0;
    }
    int m[40][40];
    int i,j,k,r,sum;
    for(i=0;i<n-1;i++){
        if(col[i]!=row[i+1]){
            cout<<"error"<<endl;
            return 0;
        }
    }
    for(i=0;i<n;i++){
        m[i][i]=0;
    }
    for(r=1;r<n;r++){
        for(j=r;j<n;j++){
            i=j-r;
            sum=m[i][i]+m[i+1][j]+row[i]*col[i]*col[j];
            for(k=i;k<j;k++){
                if(sum>m[i][k]+m[k+1][j]+row[i]*col[k]*col[j]){
                    sum=m[i][k]+m[k+1][j]+row[i]*col[k]*col[j];
                }
            }
            m[i][j]=sum;
        }
    }
    return m[0][n-1];
}

到了這里，關于【數(shù)據(jù)結構】動態(tài)規(guī)劃（Dynamic Programming）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！