动态规划经典例子_动态规划例子

基本思想

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题.但是经分解得到的子问题往往不是互相独立的。

不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。

如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

基本思想： 将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
基本要素： 最优子结构性质和重叠子问题性质

与分治法的区别：
分治算法是把原问题分解为若干个子问题，自顶向下求解子问题，合并子问题的解，从而得到原问题的解。动态规划也是把原始问题分解为若干个子问题，然后自底向上，先求解最小的子问题，把结果存在表格中，在求解大的子问题时，直接从表格中查询小的子问题的解，避免重复计算，从而提高算法效率。

矩阵连乘

问题：给定n个矩阵｛A1,A2,…,An｝，其中，Ai与Ai+1是可乘的，(i=1,2 ,…,n-1)。用加括号的方法表示矩阵连乘的次序，不同的计算次序计算量（乘法次数）是不同的，找出一种加括号的方法，使得矩阵连乘的次数最小

解决思路：
A[i:j] 表示矩阵 i 到 j 的连乘
假设在第 k 位置上找到最优解，则问题变成了两个子问题：A[i:k] , A[k+1,j]
用 m[i][j] 表示矩阵连乘的最优值，那么两个子问题对应的最优值变成 m[i][k], m[k+1][j]，且原问题的最优值为 m[1][n]。

• i=j，m[i][j] = 0
• i<j，m[i][j] = min{m[i][k] + m[k+1][j] + pi-1 * pk * pj}（i<=k<j，加上合并的计算量）

伪代码

		public static void matrixChain(int[] p,int[][] m,int[][] s){
   
			int n = p.length-1;
			for(int i=1;i<=n;i++)
				m[i][i] = 0;
			for(int r=2;r<=n;r++){
   //矩阵连乘的规模为r
				for(int i=1;i<=n;i++){
   
					int j=i+r-1;
					m[i][j] = m[i+1][j] + p[i-1]*p[i]p[j];
					for(int k=i+1;k<j;k++){
   
						int t = m[i][k]+m[k+1][j] + p[i-1]*p[i]*p[j];
						if(t<m[i][j]){
   
							m[i][j] = t;
							s[i][j] = k;
						}
					
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19