問(wèn)題描述：
給定一排數(shù)，從中按順序取出n-2個(gè)數(shù)，并且每取一次就把該數(shù)和相鄰的數(shù)相乘，然后所有的n-2個(gè)乘積相加，要求和最小。
解題思路：
考慮區(qū)間[start, end], 如果在其中取出第j個(gè)數(shù)(start+1 <= j <= end - 1)，那么在這之前j左邊的和右邊的數(shù)必然是分開(kāi)的兩個(gè)子問(wèn)題，沒(méi)有相交，于是可以得到最優(yōu)子結(jié)構(gòu)的性質(zhì)。由于是區(qū)間，可以采用記憶化搜索。
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));
}
}