矩阵连乘 n个矩阵相乘,最小化乘法运算次数? 口解空间大小 令pn为n个矩阵相乘不同计算方法的总数,则有 p(n)=1 if nE1 >p(n= keip(kp(n-k if n>1 MM2. MK(M k+1K+2n p(门)正好是 catalan数C21 解空间巨大无法枚举矩阵连乘 ◼ n个矩阵相乘，最小化乘法运算次数?  解空间大小 ➢ 令p(n)为n个矩阵相乘不同计算方法的总数，则有 ➢ p(n) = 1 if n=1 ➢ p(n) = σ𝐤=𝟏 𝐧−𝟏𝐩 𝐤 𝐩(𝐧 − 𝐤) if n>1 ➢ p(n)正好是catalan数= 𝟏 𝒏 𝑪2(𝒏−𝟏) 𝒏−𝟏 7 (M1M2 … Mk )(Mk+1Mk+2 … Mn ) 解空间巨大无法枚举