一、动态规划的基本思想

　　动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

　　将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。为了达到此目的，我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

二、动态规划的基本要素（特征）

　　1、最优子结构：

　　当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

　　2、重叠子问题：

　在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

三、用动态规划求解问题的主要步骤

　　1、找出最优解的性质，并刻画其结构特征；

　　2、递归地定义最优值（写出动态规划方程）；

　　3、以自底向上的方式计算出最优值；

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

　　说明：（1）步骤 1～3 是动态规划算法的基本步骤；
　　　　　（2）在只需要求出最优值的情形，步骤 4 可以省略；
　　　　　（3）若需要求出问题的一个最优解，则必须执行步骤  4。

四、动态规划实例

　　1、矩阵连乘问题

　　m × n 矩阵 A 与 n × p 矩阵 B 相乘需耗费的时间。我们把 m x n x p 作为两个矩阵相乘所需时间的测量值。

　　现在假定要计算三个矩阵 A、B  和 C 的乘积，有两种方式计算此乘积。

　　（1）先用 A 乘以 B 得到矩阵 D，然后 D 乘以 C 得到最终结果，这种乘法的顺序为（AB）C；

　　（2）先用 B 乘以 C 得到矩阵 E，然后 E 乘以 A 得到最终结果，这种乘法的顺序为 A（BC）。

　　尽管这两种不同的计算顺序所得的结果相同，但时间消耗会有很大的差距。

　　实例：

图1.1 A、B 和 C 矩阵

　　矩阵乘法符合结合律，所以在计算 ABC 矩阵连乘时，有两种方案，即 （AB）C  和 A（BC）。

　　对于第一方案（AB）C  和，计算：

图1.2 AB 矩阵相乘

　　其乘法运算次数为：2 × 3 × 2 = 12

图1.3 （AB）C 矩阵连乘

　　其乘法运算次数为：2 × 2 × 4 = 16
　　总计算量为：12 + 16 = 28　

　　对第二方案 A（BC），计算：

图1.4 BC 矩阵相乘

　　其乘法运算次数为：3 × 2 × 4 = 24

图1.5  A、B 和 C  矩阵连乘

　　其乘法运算次数为：2 × 3 × 4 = 24

　　总计算量为：24 + 24 = 48

　　可见，不同方案的乘法运算量可能相差很悬殊。

　　问题定义：

　　给定 n 个矩阵 {A₁, A₂, …, A_n}，其中 A_i 与 A_i+1 是可乘的，i = 1,2,…,n-1。考察这 n 个矩阵的连乘积 A₁A₂…A_n。 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。

　　这种计算次序可以用加括号的方式来确定。完全加括号的矩阵连乘积可递归地定义为：

　　（1）单个矩阵是完全加括号的；

　　（2）矩阵连乘积 A 是完全加括号的，则 A 可表示为 2 个完全加括号的矩阵连乘积 B 和 C 的乘积并加括号，即 A = (BC)。设有四个矩阵 A， B， C， D，总共有五种完全加括号的方式:   (A((BC)D))  ，  (A(B(CD)))  ，  ((AB)(CD))  ，  (((AB)C)D)  ，  ((A(BC)D))。

　　a. 找出最优解的性质，并刻画其结构特征；

　　将矩阵连乘积 A_iA_i+1…A_{j ，}简记为 A[i : j]， 这里 i≤j；考察计算 A[1:n] 的最优计算次序。

　　设这个计算次序在矩阵 A_k 和 A_k+1 之间将矩阵链断开，1 ≤ k < n，则其相应完全加括号方式为 (A₁A₂…A_k)(A_k+1A_k+2…A_n)。

　　总计算量 = A[1:k] 的计算量 +  A[k+1:n]的计算量 + A[1:k]和A[k+1:n]相乘的计算量

　　特征：计算 A[1:n] 的最优次序所包含的计算矩阵子链 A[1:k] 和 A[k+1:n] 的次序也是最优的。

　　b. 递归地定义最优值（写出动态规划方程）；

图1.6 建立递归关系

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

 1 #include <iostream>
 2 using namespace std;
 3 
 4 #define NUM 51
 5 int p[NUM];            //矩阵维数 P0 x P1,P1 x P2,P2 x P3,...,P5 x P6 
 6 int m[NUM][NUM];    //最少乘次数 / 最优值数组 
 7 int s[NUM][NUM];    //最优断开位置 
 8 
 9 void MatrixChain(int n)
10 {
11     for (int i = 1; i <= n; i++) m[i][i] = 0;
12     
13     for (int r = 2; r <= n; r++)                    //矩阵个数 
14         for (int i = 1; i <= n - r+1; i++)             //起始 
15         {
16             int j=i+r-1;                            //结尾 
17             m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];    //计算初值，从i处断开，计算最优断开位置 
18             s[i][j] = i;
19             for (int k = i+1; k < j; k++) 
20             {
21                 int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
22                 if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}
23             }
24         }
25 }
26 
27 void TraceBack(int i, int j) 
28 { 
29     if(i==j)
30         cout<<"A"<<i;
31     else 
32     {
33         cout<<"(";
34         TraceBack(i,s[i][j]); 
35         TraceBack(s[i][j]+1,j); 
36         cout<<")"; 
37     }
38 } 
39 
40 int main() 
41 {
42     int n;
43     scanf("%d", &n);
44     int i, temp;
45     for (i=0; i<n; i++)
46         scanf("%d%d", &p[i], &temp);
47     p[n] = temp;
48     MatrixChain(n);
49     printf("%d\n", m[1][n]);
50     TraceBack(1, n);
51     return 0;
52 }

[C++] 动态规划之矩阵连乘、最长公共子序列、最大子段和、最长单调递增子序列