问题描述：
给定一排数，从中按顺序取出n-2个数，并且每取一次就把该数和相邻的数相乘，然后所有的n-2个乘积相加，要求和最小。
解题思路：
考虑区间[start, end], 如果在其中取出第j个数(start+1 <= j <= end - 1)，那么在这之前j左边的和右边的数必然是分开的两个子问题，没有相交，于是可以得到最优子结构的性质。由于是区间，可以采用记忆化搜索。
dp[i][j] = min{dp[i][k] + dp[k][j] + a[i]*a[k]*a[j], i+1 <= k <= j-1}
代码如下：
#include <iostream>
using namespace std;
int dp[101][101];
int num[101];
int n;
int dfs(int s, int e)
{
if(e - s < 2)
return 0;
int i;
int Min = 1000000001;
for(i = s + 1; i <= e - 1; i++)
{
if(dp[s][i] == -1)
dp[s][i] = dfs(s, i);
if(dp[i][e] == -1)
dp[i][e] = dfs(i, e);
if(dp[s][i] + dp[i][e] + num[s] * num[i] * num[e] < Min){
Min = dp[s][i] + dp[i][e] + num[s] * num[i] * num[e];
}
}
return Min;
}
int main()
{
int i;
while(scanf("%d", &n) != EOF)
{
memset(dp, -1, sizeof(dp));
for(i = 1; i <= n; i++){
scanf("%d", &num[i]);
}
printf("%d\n", dfs(1, n));
}
}