基本思想

动态规划与分治法有相同之处。在求解问题时，也是需将原问题分解为子问题，先求子问题的最优解，然后在此基础之上求问题的最优解。但是动态规划与分治法又有不同之处。不同之处在于，在动态规划中，子问题并非相互独立，而是相互重叠在一起。在求解子问题时，一旦得到一个子问题得最优解，并不把这个子问题得最优解丢掉，而是记录到一个表格当中，在未来一旦要用到这个子问题的解，并不需要重新计算这个子问题，只需要回到表格当中，以常数时间获取这个子问题的最优解。因此动态规划法具有较高的运算效率，对相当多问题都能得到多项式时间解。

以矩阵连乘问题为例

1.矩阵：纵横排列的二维数据表格。如果一个矩阵A有p行，q列，我们称矩阵A是一个p*q的矩阵。
2.矩阵连乘问题描述：给定n个矩阵｛A1, A2, …, An｝，Ai的维数为pi-1×pi，Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

动态规划问题基本步骤

1.找出最优解的性质，并刻划其结构特征。
2.递归地定义最优值。
3.以自底向上的方式计算出最优值。
4.根据计算最优值时得到的信息，构造最优解。

图片说明

1.找出最优解的性质，并刻划其结构特征

(1)将矩阵连乘积AiAi+1...Aj简记为A[i: j]，这里i ≤ j。其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1，Ai的维数为pi-1×pi。
(2)考察计算A[i: j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全加括号方式为（AiAi+1... Ak）（Ak+1 Ak+2... Aj ）。
(3)计算量：A[i:k]的计算量加上A[k+1: j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量。

这个问题的一个关键特征是：计算A［1 :n]的最优次序所包含的计算矩阵子链A［1:k]和A「k＋1:n]的次序也是最优的。事实上，若有一个计算A[1:k］的次序需要的计算量更少，则用此次序替换原来计算A［1:k]的次序，得到的计算A［1:n]的计算量将比最优次序所需计算量更少，这是一个矛盾。同理可知，计算A［1:n]的最优次序所包含的计算矩阵子链A[k+1:n]的次序也是最优的。
因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

2.建立递归关系

设计动态规划算法的第2步是递归地定义最优值。对于矩阵连乘积的最优计算次序问题，设计算A [i: j]，1＜=i＜=j＜=n，所需的最少数乘次数为m[i][j] 。
（1）当i=j时，A[i: j]=Ai为单一矩阵无需计算，因此，m[i, i]=0，i=1,2,…,n。
（2）当i<j时，则可以利用最优子结构性质来计算m[i, j]。假如计算A[i: j]的最优计算次序在Ak和Ak+1之间断开，可以递归地定义
m[i, j]为：
图片说明
这里Ai的维数为pi-1×pi。
在计算的过程中，并不知道k的确定位置，但k的位置只有j-i种可能。

3.自底向上求计算最优值

package dynamic;

public class MatrixChain {

    public static void matrix(int[]p,int[][] m,int[][] s) {
        //p表记录各个矩阵的维数，如A1=10*5，A2=5*15,A3=15*5，那么p[0]=10,p[1]=5,p[2]=15,p[3]=5
        //m表记录A[i:j]的最小连乘积
        //s表记录最小连乘积的分割位置，如s[i][j]=1,是在1和2之间分割
        int n=p.length-1; //n为连乘矩阵个数
        for(int i=1;i<=n;i++) m[i][i]=0;//单一矩阵计算量为0，m[1][1]=m[2][2]=...=0
        for(int r=2;r<=n;r++) {  //r为矩阵连乘的个数，若r=4,则计算四个矩阵的最小连乘积
            for(int i=1;i<=n-r+1;i++) {//i为划分位置，但i的位置此时受连乘矩阵个数r和矩阵总数n的影响
                int j=i+r-1;//j为在r的情况下，最后一个连乘矩阵的下标位置
                m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];//初始分割位置为i，计算A[i:j]的连乘积
                s[i][j]=i;//记录此时的分割位置
                for(int k=i+1;k<j;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]，和分割点s[i][j]位置
                        m[i][j]=t;
                        s[i][j]=k;
                    }
                }

            }

        }
    }

    public static void traceback(int[][]s,int i,int j) {  //打印最优分割情况
        if(i==j) return;
        traceback(s,i,s[i][j]);
        traceback(s,s[i][j]+1,j);
        System.out.println("Multiply A"+i+","+s[i][j]+"and A"+(s[i][j]+1)+","+j);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] p= {30,35,15,5,10,20,25};
        int[][] m=new int[7][7];
        int[][] s=new int[7][7];
        for(int i=0;i<7;i++)
            for(int j=0;j<7;j++) {
                m[i][j]=0;
                s[i][j]=0;
            }
        matrix(p,m,s);
        traceback(s,1,6);

    }

}

过程图