动态规划法求解矩阵连乘问题 3第二步：建立递归系（递归地定义最优值） 中设：计算A[ij]所需要的最少数乘次数为m[i][j] (1≤isjsn) 则：原问题的最优值为m[1][n] 当i=j时，A[ij]=A,因此：m[i门[i]=0 Φ当i<j时，可利用最优子结构性质来计算m[]: ·设：A的维度为P-1xP,假设A[ij]的最优划分位置为k 。 则：m[=m[[k+m[k+1]]+P1PkP) k的取值只有-i个可能，即：k∈{i,i+1,,j1} k是其中使计算量达到最小的位置，因此[][们可定义为 i- i=j min {mli,k]+mlk+1,j]+pppi i< j<k<j动态规划法求解矩阵连乘问题  第二步：建立递归关系（递归地定义最优值）  设：计算A[i:j]所需要的最少数乘次数为m[i][j] （1≤i≤j≤n）  则：原问题的最优值为m[1][n]  当 i=j 时，A[i:j]=Ai，因此：m[i][i]=0  当 i<j 时，可利用最优子结构性质来计算m[i][j]： • 设：Ai 的维度为 Pi-1 x Pi ，假设A[i:j]的最优划分位置为k • 则：m[i][j]=m[i][k]+m[k+1][j]+ Pi-1 Pk Pj • k的取值只有j-i个可能，即：k∈{i, i+1, ..., j-1} • k是其中使计算量达到最小的位置，因此m[i][j]可定义为     + + +  = = −   m i k m k j p p p i j i j m i j i k j min{ [ , ] [ 1, ] } 0 [ , ] 1 i k j