对维数为序列<5, 10, 3, 12, 5, 50, 6>的各矩阵,找出其矩阵链乘积的一个最优加全部括号。 m[1,2]=5*10*3=150, s[1,2]=1; m[2,3]=10*3*12=360, s[2,3]=2; m[3,4]=3*12*5=180, s[3,4]=3; m[4,5]=12*5*50=3000, s[4,5]=4; m[5,6]=5*50*6=1500, s[5,6]=5; m[1,3]=min(5*10*12+m[2,3], m[1,2]+5*3*12)=min(600+360, 150+180)=330, s[1,3]=3; m[2,4]=min(10*3*5+m[3,4], m[2,3]+10*12*5)=min(150+180, 360+600)=330, s[2,4]=3; m[3,5]=min(3*12*50+m[4,5], m[3,4]+3*5*50)=min(1800+3000, 180+750)=930, s[3,5]=5; m[4,6]=min(12*5*6+m[5,6], m[4,5]+12*50*6)=min(360+1500, 3000+3600)=1860, s[4,6]=6; m[1,4]=min(5*10*5+m[2,4], m[1,2]+m[3,4]+5*3*5, m[1,3]+5*12*5)=min(250+330, 150+180+75, 330+300)=405, s[1,4]= 3; m[2,5]=min(10*3*50+m[3,5], m[2,3]+m[4,5]+10*12*50, m[2,4]+10*5*50)=min(1500+930, 360+3000+6000, 330+2500)=2430, s[2,5]=3; m[3,6]=min(3*12*6+m[4,6], m[3,4]+m[5,6]+3*5*6, m[3,5]+3*50*6)=min(216+1860, 180+1500+90, 930+900)=1830, s[3,6]=6; m[1,5]=min(5*10*50+m[2,5], m[1,2]+m[3,5]+5*3*50, m[1,3]+m[4,5]+5*12*50, m[1,4]+5*5*50)=min(2500+2430, 150+930+750, 330+3000+3000, 405+1250)=1655, s[1,5]=5; m[2,6]=min(10*3*6+m[3,6], m[2,3]+m[4,6]+10*12*6, m[2,4]+m[5,6]+10*5*6, m[2,5]+10*50*6)=min(180+1830, 360+1860+720, 330+1500+300, 2430+3000)=2010, s[2,6]=3; m[1,6]=min(5*10*6+m[2,6], m[1,2]+m[3,6]+5*3*6, m[1,3]+m[4,6]+5*12*6, m[1,4]+m[5,6]+5*5*6, m[1,5]+5*50*6)=min(300+2010, 150+1830+90, 330+1860+360, 405+1500+150, 1655+1500)=2055, s[1,6]=5; 结果:((A1A2)(A3A4))(A5A6)