前言
新的一年，好好学习。
正文
问题来源
本问题来自看书时有个问题是求矩阵相乘的最小次数，之前算法课老师有讲这个问题（使用的教材是《计算机算法分析与设计》王晓东版）。当时是弄懂了，现在又忘了，借此机会来温故一下。
问题描述
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
示例 1：
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2：
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
分析：
1找出最优解的性质，并刻画其结构特征
这是设计动态规划算法的第一步，我们可以将矩阵连乘积AiAi+1……Aj记为A[i：j]。问题就是计算A[1：n]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1 <= k < n ,使其完全加括号方式为（（A1……Ak）（AK+1……An）），这样就将原问题分解为两个子问题，，按此计算次序，计算A[1：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]这两个子问题的最优计算次序，以此类推，将A[1：k]和A[k+1：n]递归的分解下去，求出每个子问题的最优解，子问题的最优解相乘便得到原问题的最优解。
2递归地定义最优值
这是动态规划的第二步，对于矩阵连乘积的最优计算次序的问题，设计算A[i：j]，1<=i<=j<=n,所需要的最小数乘次数为m[i][j]，则原问题的最优值为m[1][n]。
当i=j时，A[i：j]=Ai为单一的矩阵，则无需计算，所以m[i][j]=0，i=j=1，2，……，n。即对应的二维表对角线上的值全为0。
当i < j时，这就需要用步骤（1）的最优子结构性质来计算m[i][j]。若计算A[i:j]的最优次序在Ak和Ak+1之间断开，i<=k < j,则m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj,k的位置只有j-i种可能，即k属于集合{i，i+1，……，j-1}，所以k是这j-i个位置中使计算量达到最小的那个位置。
所以m[i][j]可以递归地定义为 m[i][j]={ 0 ， i == j
min{m[i][k]+m[k+1][j]+pi-1*pk*pj ， i < j ,i <= k < j }
将对应于m[i][j]的断开位置k记为s[i][j]，在计算出最优值m[i][j]后，可递归地由s[i][j]构造出相应的最优解
3以自底向上的方式计算出最优值
动态规划的一大好处是，在计算的过程中，将已解决的子问题答案保存起来，每个子问题只计算一次，而后面的子问题需要用到前面已经解决的子问题，就可以从表中简单差出来，从而避免了大量的重复计算
func matrixChain(p []int) ([][]int, [][]int) {
l := len(p)
m := make([][]int, l)
s := make([][]int, l)
for i :=0; i < l; i++ {
m[i] = make([]int, l)
s[i] = make([]int, l)
}
for r := 2; r < l; r++ {//
for i := 1; i < l - r + 1; i++ {
j := r + i - 1
m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j] //m[i][i] = 0 is omited
s[i][j] = i
var t int
for k := i + 1; k < j; k++ {
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
}
}
}
}
return m, s
}
func trackback(i, j int, s [][]int) {
if i == j {
return
}
trackback(i, s[i][j], s)
trackback(s[i][j]+1, j, s)
fmt.Println("Multiply A", i, ",", s[i][j], " and A", s[i][j]+1, ",", j)
}
总结：
勤思考。
结语
不管怎么样好好加油。
