地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1602
题意：一排牌/卡片（一串数字），每次从这些牌中拿走一张牌（首尾两张不能拿），把前一张，这一张，后一张牌上的数字相乘的结果累加，直到只剩下两张牌为止。问所能得到的最小结果是多少。
例如：5张牌是10，1，50，20，5。拿走的牌的顺序如果是50，20，1。得到的结果就是：
1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150;
分析：此题目属于动态规划（DP），和矩阵乘法加括号的命题高度类似，也许就是从矩阵乘法变形出来的。
PS：但我却一时没能分析清楚，最后用了很复杂的方法 DP，结果却 WA。忍不住搜索了这道题目，才通过，对我的自信心造成个不小的打击。为什么一层窗户纸我就是没能捅破呢，差之毫厘的距离。不过要吸取教训，加强学习。自己的思维有一个盲点，然后一直转入牛角尖又出不来，越想越复杂了。尽管题目比较复杂是很常见的，但这题应该不止于此，过的数量那么多，后来看到网上还有人称之为水题，的确是水题。感叹自己的思维还是死板了。由于这题是参考过网上，所以这个就不能算作自己做出来的题目，就没有 AC 数增加的喜悦感。
递推式是 DP 的核心，得到递推式也就基本得到了 DP 的代码。DP 问题的特征是最优子结构，即问题包含多个子问题，问题的最优解中包含子问题的最优解。求解过程中相同的子问题可能多次被遇到，把已经求出答案的子问题的解记录到表中，这样问题的复杂度通常从指数降低到多项式。
（1）规模最小的子问题最容易，是三个数字，结果是三个数字的乘积。
（2）为了把问题分解成规模更小的子问题，定义问题如下，给出一个整数数组 c [ ]，求索引从 i 到 j 范围的一串卡片操作到最后得到的最小结果是 s[i][j]，问题规模是卡片数，即 j - i - 1;
（3）类似矩阵乘法，现在把 s[i][j] 从中间某个位置（i < k < j）分裂成规模更小的两个子问题，即是把数字串的长度减小：
c[i], ..., c[k], ..., c[j]; （ c[k] 是最后取走的牌 ）
先把 c[i] , ... , c[k] 中间的所有数字取走，根据问题定义得到结果是 s[i][k]; 剩下的是 c[i], c[k], ..., c[j];
再把 c[k], ... , c[j] 中间的所有数字取走，根据问题定义得到结果是 s[k][j]; 剩下的是 c[i], c[k], c[j];
最后取走 c[k]；因此如果最后取走 k ，则 s[i][j] = s[i][k] + s[k][j] + c[i]*c[k]*c[j];
因此这就是要找的递推式：（由于题目要求得到的结果最小，因此下面的式中取最小值）
s[i][j] = min ( s[i][k] + s[k][j] + c[i]*c[k]*c[j] ); ( i < k < j )
从上式可以看到，子问题的最优解是最终问题的最优解的一部分。
解法和矩阵乘法相同，都是从下至上求解（子问题规模从小到大），即先求解最小的问题，逐渐叠加上去，直到得到最终的规模问题的解。在此题中问题规模是数字串包含的数字个数，从 3 一直增加到卡片总数。在求解问题规模为 j - i + 1 的所有问题时，依赖更小规模的子问题，也就是说所有长度小于 j - i + 1的子问题都应该已求解完毕。从矩阵 s 来看，是从近对角线位置依次求解到矩阵右上角。
zoj1602
#include <stdio.h> #include <stdlib.h> #include <string.h> /* scores */ unsigned int s[100][100]; /* cards' point */ int c[100]; void GetScores(int card_count) { int i, j, k, t; unsigned int tmp; /* init */ memset(s, 0, sizeof(s)); for(k = 3; k <= card_count; k++) { for(i = 0; i < card_count - 2; i++) { j = i + k - 1; s[i][j] = 0xffffffff; for(t = i + 1; t < j; t++) { tmp = s[i][t] + s[t][j] + c[i]*c[t]*c[j]; if(tmp < s[i][j]) { s[i][j] = tmp; } } } } } int main(int argc, char* argv[]) { int i, card_count = 0; while(scanf("%ld", &card_count) != EOF) { for(i = 0; i < card_count; i++) scanf("%ld", c + i); GetScores(card_count); printf("%lu\n", s[0][card_count-1]); } return 0; }
参考：
（1）ZOJ 1602 Multiplication Puzzle (DP)： http://blog.csdn.net/fangjiaguo/article/details/6648738
