【数据结构】动态规划（Dynamic Programming）

一.动态规划（DP）的定义：

求解决策过程（decision process）最优化的数学方法。

将多阶段决策过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。

二.动态规划的基本思想：

与分治法类似，将待求解问题分解成若干个子问题。

但是经分解得到的子问题往往不是相互独立的。

如果使用分治法求解问题，有些子问题被重复计算了多次。

而“如何减少子问题的重复计算”是动态规划算法的关键思想。

问题：如何减少子问题的重复计算呢？

解决方案：保存已解决的子问题的答案，在需要的时候找出已经求得的答案。

三.动态规划的基本步骤

1.找出最优解的性质，并刻划其结构特征。即：寻找最优解的子问题结构。

2.递归地定义最优解。即：根据子问题的结构建立问题的递归解式，求解最优值。

3.以自底向上的方式计算出最优值。

4.根据计算最优值时得到的信息，构造最优解。

四.例题分析——多个矩阵连乘模块设计

问题描述：

实现多个矩阵连乘功能

关键问题计算：

给定n个矩阵{}，其中与是可乘的，考察这n个矩阵的连乘积

由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。

若一个矩阵连乘积的计算次序完全确定，也就是说该矩阵已完全加括号，则可以依此次序反复调用3个矩阵相乘的标准算法计算出矩阵连乘积。

完全加括号的矩阵连乘积：

设有四个矩阵 A，B，C，D 维数分别为：

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次乘法计算！

矩阵连乘问题转化为：

确定矩阵连乘的计算次序，使得按照该次序计算矩阵连乘需要的数乘次数最少。

1.穷举法求解思路：

        列举出所有可能的计算次序，并计算出每一种次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。

算法复杂度分析：

对于n个矩阵的连乘积，设其不同的计算次序为P（n）

由于每种加括号方式都可以分解为两个子矩阵的加括号的问题

2.动态规划求解：

最优解结构分析：

将矩阵连乘积简记为：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]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。

最优子结构性质：最优解包含其子问题的最优解。

建立递归关系：(m[i,j]表示最小连乘次数）

当i=j时，A[i:j]=,m[i,j]=0

当i<j时，m[i,j]={m[i,k]+m[k+1,j]+}

则有：

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

注：由于矩阵乘法中的列数和的行数相等，则可以只用列数来化简表达式，这里的均表示第i-1，k，j个矩阵的列数。n个矩阵的信息，只需要一个长度为n+1的数组来表示即可。

对于m[i][j]数组，只需要填入上三角中的元素即可（因为i<=j）。

五.代码实现

#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];
}