Multiplication Puzzle POJ - 1651 （动态规划）

链接
分析：依次从左到右给你n个数字，每次取出一个数字（这个数字不能是最两边的数字），
这个数字和它左右两边的数字（一共三个数字）相乘，累加这个数。直到最后仅剩下两个数字。求最后累加的最小值。
对于整个牌的序列，最左端和最右端的牌是不能被取走的，除这两张以外的所有牌，必然有一张最后取走。取走这最后一张牌有一个仅与它本身以及最左端和最右端的牌的值有关的得分，这个分值与其他牌没有任何关系。当这张最后被取走的牌被定下来以后（假设位置为j）, 最左端到j之间的所有牌被取走时所造成的得分必然只与这之间的牌有关从而与j到最右端之间的牌独立开来。这样就构成了两个独立的子区间，出现重叠子问题。于是问题的解就是取走最后一张牌的得分+两个子区间上的最小得分
不妨假设当前区间为[b, e],在(b,e)之间枚举最后一张被取走的牌，通过最优子问题求出当前区间的最优解：

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[110][110],sum[110];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d", &sum[i]);
for(int len=0;len<=n-2-1;len++)
{
for(int i=2;i<=n-1;i++)
{
int j=i+len;
if(j>=n)
break;
dp[i][j]=100000000;
for(int k=i;k<=j;k++)
{
dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+sum[i-1]*sum[k]*sum[j+1]);
}
}
}
printf("%dn", dp[2][n-1]);
}

最后

以上就是称心书本为你收集整理的Multiplication Puzzle POJ - 1651 （动态规划）的全部内容，希望文章能够帮你解决Multiplication Puzzle POJ - 1651 （动态规划）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。