问题描述:
给定一排数,从中按顺序取出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>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dp[101][101];
int num[101];
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dfs(int s, int e)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if(e - s < 2)
return 0;
int i;
int Min = 1000000001;
for(i = s + 1; i <= e - 1; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(dp[s][i] == -1)
dp[s][i] = dfs(s, i);
if(dp[i][e] == -1)
dp[i][e] = dfs(i, e);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i;
while(scanf("%d", &n) != EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
memset(dp, -1, sizeof(dp));
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; i <= n; i++)
{
scanf("%d", &num[i]);
}
printf("%d\n", dfs(1, n));
}
}