算法设计第三次上机作业-Multiplication Puzzle

题目描述

给出一排写有数字的卡片，每次都从这排卡片中抽取一张拿出（不能拿第一张和最后一张），将该卡片上的数字和其旁边的两个数字进行相乘，重复该过程直到最后只剩下第一张卡片和最后一张卡片。使得乘数相加得到的和最小。 例如，卡片上的数字为10 1 50 20 5, 如果抽取顺序为 1，20，50，那么最终得到的结果为 10x1x50 + 50x20x5 + 10x50x5 = 500+5000+2500 = 8000 如果抽取顺序为50，20，1，那么最终的结果为 1x50x20 + 1x20x5 + 10x1x5 = 1000+100+50 = 1150.

输入 第一行为N，代表共有N张卡片 第二行给出N个数字

输出 得到的最小的乘积和

解题思路

将该问题拆成小问题，那么最小的问题就是三个数字的情况。用一个二维数组d[i][j]来记录从i到j的最小乘积和，则该问题的最小子问题就是最后取走的元素是第k个元素，也就是d[i][j] = d[i][k] + d[k][j] + a[i]*a[j]*a[k] (i<k<j)

AC代码

// // main.cpp // homework3.6 // // Created by dongyu on 2019/10/31. // Copyright © 2019 dongyu. All rights reserved. // #include <iostream> #include <cstdio> #include <cmath> #define Max 105 const int INF = 2147483647; using namespace std; int d[Max][Max]; /*int solve(int input[], int i, int j) { if(j == i+1) return 0; int temp, min_value = INF; for(int k=i+1; k<j; k++) { temp = solve(input, i, k) + solve(input, k, j) + input[i]*input[j]*input[k]; if(temp < min_value) min_value = temp; } return min_value; }*/ int main(int argc, const char * argv[]) { // insert code here... int N; int input[Max], d[Max][Max]; cin>>N; for(int i=0; i<N; i++) { scanf("%d", &input[i]); } for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { d[i][j] = 0; } } for(int k=2; k<N; k++) { for(int i=0; i<N-k; i++) { //j=i+k int temp, min_value = INF; for(int m=i+1; m<i+k; m++) { temp = d[i][m] + d[m][i+k] + input[i]*input[m]*input[i+k]; if(temp < min_value) min_value = temp; } d[i][i+k] = min_value; } } cout<<d[0][N-1]<<endl; return 0; }

如果用递归的方法那么就是注释掉的那个函数，但是如果用递归的方法会TLE。所以动态规划就在于把每一步的结果都记录下来了，这样就可以避免每次用到这些数字的时候都计算一遍。