这道题其实非常的好，考察一个人对矩阵的掌握程度。不会做的回去看《高等代数》。
我的理解是把相邻的两个数看作矩阵的长宽。例如矩阵 a1 * a2 ,a2 *a3.....an-1 * an;
两个矩阵相乘 ，有：(n×m)*(m×p)变成 n×p的矩阵。这样就把m  取掉了。
对 a[i,j]为c[i] ×c[j+1] 的矩阵。这样a[1,n-1]就为 第一个数乘以最后一个数了c[1]*c[n]。
取其中的一个k.假设最小。 a[i,k] + a[k+1, j] + c[i]*c[k+1]*c[j+1];
a[i,k] 和 a[k+1,j] 分别是最优解.他们合并为a[i,j]的时候去掉了c[k+1].代价是c[i]*c[k+1]*c[j+1];
a[i,k] 和 a[k+1,j]  易证得分别为最优子结构，相互独立。
好难想。可能是我太水了。

• Re:此题虽水，但我人更水。在此非常感谢winsweet 师兄。 (401) 656766896 2012-02-29 21:09:12