POJ 1651 Multiplication Puzzle
题目描述：给你n个数，拿走一个数，会获得一个值，该值是这个数*它左边的数*它右边的数，最后的结果是取走中间n-2个数所获得的值的和。因为选取的顺序不一样，所获得的值也不一样，求取走中间n-2个值，最小的结果。
解题分析：其实就是类似矩阵连乘的思想，矩阵连乘中选取k作为最后一次乘法的中间矩阵，在这个题中选取第k个数作为最后一次乘法的中间数，那么问题转化为求区间[i,k]和区间[k,j]的最优解 + 这个乘积，状态转移方程就出来了：
ans = min(ans,dp[i][k] + dp[k][j] + num[i]*num[k]*num[j]);像这种第一层循环是枚举长度的转移方法，还是记忆化搜索更好写。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100 + 10;
int dp[maxn][maxn];
int num[maxn];
int n;
int dfs(int u,int v)
{
if(dp[u][v] > -1) return dp[u][v];
if(v - u <= 1) return dp[u][v] = 0;
int ans = INF;
for(int i = u + 1; i <= v - 1; i++)
{
ans = min(ans,dfs(u,i) + dfs(i,v) + num[u]*num[i]*num[v]);
}
return dp[u][v] = ans;
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%d",&num[i]);
}
memset(dp,-1,sizeof(dp));
dfs(1,n);
printf("%d\n",dp[1][n]);
return 0;
}
迭代的代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100 + 10;
int dp[maxn][maxn];
int num[maxn];
int n;
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%d",&num[i]);
}
memset(dp,0,sizeof(dp));
for(int l = 1; l <= n - 2; l++)//枚举中间元素的长度
{
for(int i = 1; i + l + 1<= n; i++)//枚举起点
{
int j = i + l + 1;//终点
int ans = INF;
for(int k = i + 1; k <= j -1; k++)//枚举中间元素，它的意思是最后一个选择的元素
{
ans = min(ans,dp[i][k] + dp[k][j] + num[i]*num[k]*num[j]);
}
dp[i][j] = ans;
}
}
printf("%d\n",dp[1][n]);
return 0;
}
投递蔚来等公司10个岗位 >
腾讯公司福利 457人发布