###纪小七###

First of all：不知那年那月那日，我纪小七也头脑开窍、屁股开花了…这辈子一定要挣钱滋润自己！！！

---

讲一哈：动态规划

（1）动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到远问题的解。（2）与分治法不同的是适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。（3）若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指数时间。（4）动态规划适用于解最优问题。

---

矩阵连乘问题

【问题描述】

给定n个矩阵{A1,A2,…,An},其中，Ai与Ai+1是可乘的，i=1,2，…，n-1。考查这n个矩阵的连乘积。

1、分解最优解的结构

第一步：刻画该问题的最优解结构特征。
【标记】方便起见，将矩阵连乘积AiAi+1…Aj简记为A【i:j】。

=======>考察计算A【1：n】的最优计算次序。

设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1<=k<n,则其相应的完全加括号为：
（（A1…Ak）（Ak+1…An））

因此，总计算量==A[1:k]的计算量+A[k+1：n]的计算量+A[1：k]和A[k+1：n]相乘的计算量。

关键特征：计算A[1：n]的最有次序包含的计算矩阵子链A[1：k]和A[k+1：n]的次序也是最优的！

2、建立递归关系

第二步:递归的定义最优值。
【标记】设计算A[i:j]，1<=i<=j<=n，所需的最少数乘次数为m[i][j]，则原问题的最优值为m[1][n]。

3、计算最优值

动态规划算法matrixchain：

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++) {for (int i = 1; i <= n - r + 1; i++) {int j = i + r - 1;m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[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] = t;s[i][j] = k;}}}}

4、构造最优解

	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);}

完整代码：

package 矩阵连乘;/*** array[i][j]* 		表示Ai...Aj的最佳计算次序所对应的相乘次数 即存放各子问题的最优值* s[i][j]=k* 		表示Ai...Aj这(j-i+1)个矩阵中最优加括号方法为(Ai...Ak)(Ak+1...Aj),* 		即存放了各子问题的最优决策* p[i]表示Ai的行数，p[i+1]表示Ai的列数 * @author 光*/
public class Strassen{private int m[][];  private int p[];  private int s[][];  public  Strassen(){//六个矩阵有七个数p=new int[]{30,35,15,5,10,20,25};  m=new int[6][6];  s=new int[6][6];  }  /**动态规划*/public void martixChain(){  int n=m.length;  for(int i=0;i<n;i++){m[i][i]=0;}for(int r=2;r<=n;r++){  		//不同规模的子问题for(int i=0;i<=n-r;i++){    //每一个规模为r的矩阵连乘序列的首矩阵Aiint j=i+r-1;  			//每一个规模为r的矩阵连乘序列的尾矩阵Aj// 决策为k=i的乘法次数m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1];  s[i][j]=i;for(int k=i+1;k<j;k++){ //对Ai...Aj的所有决策，求最优值，记录最优决策int t=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j];  if(t<m[i][j]){  m[i][j]=t;s[i][j]=k;}  }  }  }  }  /* * 待求矩阵为：Ai...Aj*/  public void traceBack(int i ,int j){if(i<j){traceBack(i,s[i][j]);traceBack(s[i][j]+1,j);if(i==s[i][j] && (s[i][j]+1)==j){System.out.println("把A"+(i+1)+"到A"+(j+1)+"括起来");}else if(i==s[i][j] && (s[i][j]+1)!=j){System.out.println("把A"+((s[i][j]+1)+1)+"到A"+(j+1)+"括起来,在把A"+(i+1)+"到A"+(j+1)+"括起来");}else if(i!=s[i][j] && (s[i][j]+1)==j){System.out.println("把A"+(i+1)+"到A"+(s[i][j]+1)+"括起来,再把A"+(i+1)+"到A"+(j+1)+"括起来");}else{System.out.println("把A"+(i+1)+"到A"+(s[i][j]+1)+"括起来，再把A"+((s[i][j]+1)+1)+"到A"+(j+1)+"括起来，然后把A"+(i+1)+"到A"+(j+1)+"括起来");}}}public static void main(String[] args) {  Strassen m=new Strassen();  m.martixChain();m.traceBack(2, 5);}
}