动态规划和分治法类似，基本思想是将问题划分成若干子问题，先求子问题，然后结合子问题的解得到原问题的解。
与分治法的区别是，使用动态规划的问题 子问题之间不相互独立。 所以用一个表来记录已经解决的子问题答案，避免重复计算。
动态规划算法适用于解最优化问题，通常按照4个步骤设计：
1.找出最优解的性质，并刻画其结构特征；
2.递归地定义其最优值；
3.以自底向上地方式计算最优值；
4.根据计算最优值时得到的信息，构造最优解（如果需要最优解）。
具体的例子：
矩阵连乘问题
问题描述：
给定n个矩阵：A1,A2,...,An，其中Ai与Ai+1是可乘的（i=1，2...，n-1）。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。
1.分析最优解的结构
首先要知道矩阵的基本知识，
矩阵A和矩阵B可乘的条件是A的列数等于B的行数，若A是p*q 矩阵，B是q*r矩阵，则其乘积C=AB是一个p*r的矩阵，
计算次数（乘法次数）是p*q*r次。
我们（通过加括号的方式）改变矩阵乘法的次序，可以改变计算次数。
因此，使得乘法计算次数最少问题就变成了一个如何加括号的问题。
记矩阵连乘积AiAi+1...Aj 为A[i:j]
设这个矩阵在Ak (1<=k<n)处加括号，得到(A1A2...Ak) (Ak+1Ak+2...An)
于是分解成两个规模较小的子问题A[1:K] A[k+1:n]。若要A[1:n]计算次数最少，则子问题A[1:k] A[k+1:n]计算次数也应该最少。
因此，该问题的最优解包含了其子问题的最优解。这种性质称为最优子结构性质。
2. 建立递归关系
m[i][j] = 0, i = j;
= min { m[i][k] + m[k+1][j] + pi-1pkpj}, i<=k<j,i<j;
3. 计算最优值
这里计算次序可以通过手工画m这张表来找到规律。
/* 输入参数： 一维数组p：各矩阵维数 整数n：矩阵个数 二维数组m：存储子问题的最优值 二维数组s：记录最优断开位置（用于得到最优解） 函数功能：生成最优值表m和断开位置表s; */ void MatixChain(int *p, int n, int **m, int **s) { //先把m这张表的对角线赋值0. for (int i = 1; i <= n; i++) m[i][i] = 0; /*沿对角线方向进行构造m。 *i是行，j是列，r可以看成是第r条对角线 *i和j的取值规律是根据对角线变化的规律来的，比如第2条对角线上，i和j相差1，第3条对角线上，i和j相差2 可以得出第r条对角线上,i和j相差r-1，即 j = i + r-1 */ for (int r = 2; r <= n; r++) { for (int i = 1; i <= n - r + 1; i++) { int j = i + (r - 1); //通过递归式，给m[i][j]赋值 int k = i; m[i][j] = m[i][k]+ m[k + 1][j] + p[i - 1] * p[k] * p[j]; s[i][j] = k; for (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] = t; s[i][j] = k; } } } } }
4.构造最优解
void Traceback(int i, int j, int **s) { if (i == j) 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; } /* 注：Multiply A i , s[i][j] and A (s[i][j]+1), j 就 是Ai...A(s[i][j] 和 A(s[i][j]+1)...j相乘 比如Multiply A1, 3 and A4, 6 就是 (A1A2A3) (A4A5A6) */
维数： int p[] = {30,35,15,5,10,20,25};
#include<iostream> using namespace std; /* 输入参数： 一维数组p：各矩阵维数 整数n：矩阵个数 二维数组m：存储子问题的最优值 二维数组s：记录最优断开位置（用于得到最优解） 函数功能：生成最优值表m和断开位置表s; */ void MatrixChain(int *p, int n, int **m, int **s) { //先把m这张表的对角线赋值0. for (int i = 1; i <= n; i++) m[i][i] = 0; /*沿对角线方向进行构造m。 *i是行，j是列，r可以看成是第r条对角线 *i和j的取值规律是根据对角线变化的规律来的，比如第2条对角线上，i和j相差1，第3条对角线上，i和j相差2 可以得出第r条对角线上,i和j相差r-1，即 j = i + r-1 */ for (int r = 2; r <= n; r++) { for (int i = 1; i <= n - r + 1; i++) { int j = i + (r - 1); //通过递归式，给m[i][j]赋值 int k = i; m[i][j] = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; s[i][j] = k; for (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] = t; s[i][j] = k; } } } } } //根据s表生成最优解，使用递归 void Traceback(int i, int j, int **s) { if (i == j) 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() { const int n = 6; int p[] = {30,35,15,5,10,20,25}; int **m = new int*[n+1] ; int **s = new int*[n+1]; for (int i = 0; i < n + 1; i++) { m[i] = new int[n + 1] ; s[i] = new int[n + 1]; } for (int i = 1; i < n + 1; i++) { for (int j = 1; j < n + 1; j++) { m[i][j] =0; s[i][j] = 0; } } MatrixChain(p,n,m,s); //这里我把构造出来的m表打出来了 for (int i = 1; i < n + 1; i++) { for (int j = 1; j < n + 1; j++) { printf("%8d", m[i][j]); } cout << endl; } //输出最优解 Traceback(1, 6, s); return 0; }
