矩阵连乘 o m[i,j]=minisksifm[i, k]+m[k+1,j]+rixrkxri), if i< nm[i]=0, if Fi m个,m1,2]m1,3m41m[个 m22m23m24m25 3, 3]m[3, 41 m[3, 51 m[441m[451 m[,51 11
矩阵连乘 m[i,j] = mini≤k<j{m[i,k] + m[k+1,j] +rirkrj }, if i<j m[i,j] = 0, if i=j 11 m[1,1] m[1,5] m[4,4] m[5,5] m[2,2] m[3,3] m[4,5] m[3,4] m[2,3] m[1,2] m[1,3] m[2,4] m[3,5] m[1,4] m[2,5]
矩阵连乘 Matrix-Chain-Order(r) n=length(o) 自底向上方法 for j=1 to n do m[, 1=0 for x1 to n- do for i=1 to n-x do 」=|+x m for k=i to j-1 do q=m[i,k]+m[k+1,j+1 if q<m[i, j] then m[小]=q; [】]=k; return m and s 12
矩阵连乘 12 Matrix-Chain-Order(r) n=length(r)； for i=1 to n do m[i, i]=0; for x=1 to n-1 do for i=1 to n-x do j = i+x; m[i, j] = ∞; for k=i to j-1 do q = m[i, k]+m[k+1, j]+ri-1 rk rj if q<m[i, j] then m[i,j]=q; s[i,j]=k; return m and s 自底向上方法
矩阵连乘 mN,N],sN,N]赋1; MatriXChain(,j) 递归备忘录方法 if i=i then m[i,j=0; return m[]=00 for k=i to j-1 do a=m[i,k];b=m收k+1,j if a==-1 then a=MatriX Chain(i, k) if b==-1 then b= MatriXChain(k+1, j) g=a+b+rrkr if q<m[i, j] then m[i】]=q; s[]=k; 13
矩阵连乘 13 m[N,N], s[N,N] 赋-1; MatrixChain (i, j) if i=j then m[i, j]=0; return; m[i, j] = ∞; for k=i to j-1 do a = m[i, k]; b = m[k+1, j]; if a == -1 then a = MatrixChain(i, k); if b == -1 then b = MatrixChain(k+1, j); q = a + b + ri-1 rk rj if q<m[i, j] then m[i,j]=q; s[i,j]=k; 递归备忘录方法
钢条切割 长度为n英寸的钢条进行切割,可有很多切法 n1段4英寸 4段1英寸 口2段2英寸 n13英寸1段1英寸 ■假设有一张价格表 匚长度1 3 4 价格pi 9 将这4英寸的钢条切成2段2英寸的,收益最大,为10 14
钢条切割 ◼ 长度为n英寸的钢条进行切割，可有很多切法 1段4英寸 4段1英寸 2段2英寸 1段3英寸1段1英寸 ◼ 假设有一张价格表 14 长度i 1 2 3 4 价格pi 1 5 8 9 将这4英寸的钢条切成2段2英寸的，收益最大，为10
钢条物割 问题定义 口给定一段长度为n英寸的钢条和一个价格表pi (i=1,2,n),给定切割方案,使收益最大 15
钢条切割 ◼ 问题定义 给定一段长度为n英寸的钢条和一个价格表pi (i=1,2,…,n)，给定切割方案，使收益最大 15