矩阵连乘 n个矩阵相乘,最小化乘法运算次数? 口但是,若可分别得到MM2M和M+M+2Mn的 最小乘法次数,则可以得到在k处断开的连乘方法 (MM2M)(Mk+1M+2M的最小乘法次数 令MM2…M的最小乘法次数为m1k] k+1k+2 Mn的最小乘法次数为m[k+1n] 则k处断开的最少乘法数m[1,k]+mk+1,n]+r1×c1xcn 具有最优子结构: 问题的最优解包括子问题最优解矩阵连乘 ◼ n个矩阵相乘，最小化乘法运算次数?  但是，若可分别得到M1M2 … Mk和Mk+1Mk+2 … Mn的 最小乘法次数，则可以得到在 k处断开的连乘方法 (M1M2 … Mk )(Mk+1Mk+2 … Mn )的最小乘法次数 ➢ 令M1M2 … Mk的最小乘法次数为m[1,k] ➢ Mk+1Mk+2 … Mn的最小乘法次数为m[k+1,n] ➢ 则k处断开的最少乘法数m[1,k] + m[k+1,n] +r1ckcn 8 具有最优子结构： 问题的最优解包括子问题最优解