对于整个牌的序列，最左端和最右端的牌是不能被取走的，除这两张以外的所有牌
，必然有一张最后取走。取走这最后一张牌有一个仅与它本身以及最左端和最右端的
牌的值有关的得分，这个分值与其他牌没有任何关系。当这张最后被取走的牌被定
下来以后（假设位置为j）, 最左端到j之间的所有牌被取走时所造成的得分必然只与
这之间的牌有关从而与j到最右端之间的牌独立开来。这样就构成了两个独立的子
区间，出现重叠子问题。于是问题的解就是
               取走最后一张牌的得分+两个子区间上的最小得分
不妨假设当前区间为[b, e],在(b,e)之间枚举最后一张被取走的牌，通过最优子问题
求出当前区间的最优解：
        opt[b][e] = min{ opt[b][j]+opt[j][e] + val(b,j,e); };
                                                b+1<= j <=e-1
val(b,j,e)是取走j所造成的得分，即第b,j,e这三张牌的积。
空间o(n^2), 时间o(n^3)

• 这题不是经典的矩阵相乘的问题吗？ (521) Sempr 2006-07-29 16:33:55
  • Re:这题不是经典的矩阵相乘的问题吗？ (11) o_oXo_o 2006-07-29 16:36:39
  • Re:这题不是经典的矩阵相乘的问题吗？ (20) scu_try 2007-03-05 15:25:13
  • 还是没明白 (0) ASCII 2007-04-16 21:39:06
    • 算法导论331页 15.2 (0) Sempr 2007-04-16 22:22:59
      • Re:算法导论331页 15.2 (15) stm512 2007-07-14 15:11:11
  • Re:这题不是经典的矩阵相乘的问题吗？ (12) eulerray 2007-08-13 09:37:19
  • Re:这题不是经典的矩阵相乘的问题吗？ (8) E07610113 2008-11-23 12:28:23
  • Re:这题不是经典的矩阵相乘的问题吗？ (5) calme 2009-08-15 21:56:50
• Re:请教这道题怎么dp? (521) hellobuy 2007-03-23 21:41:23
• thx (521) ASCII 2007-04-16 21:38:25
• Re:请教这道题怎么dp? (1) boys 2008-11-23 15:12:32
• Re:请教这道题怎么dp? (13) tanghaibao 2008-12-31 04:32:08
• 高手。。。 (0) tog 2010-07-14 11:53:56