n个数字乘法运算的最小和

---

在本文中，我们将讨论两种生成所需总和的方法。这两种方法都是基于动态规划的方法。在第一种方法中，我们将使用备忘录来进行动态规划，然后我们将对表格法应用相同的方法，以避免为递归使用额外的堆栈空间。

问题陈述

给定一个包含 n 个整数的列表，我们的目标是通过重复执行以下操作来最小化乘法运算的总和：每次取两个相邻的数字，将它们模 100 求和，并将结果替换回列表中，直到列表中只剩下一个数字。

让我们考虑输入 [30, 40, 50] 并计算乘法运算的最小和。

为了找到最小和，我们将探索不同的可能性 -

情况 1 - 取 30 和 40

乘法：30 * 40 = 1200

并将 (30 + 40)%100= 70 放回

执行此操作后，列表变为：70, 50

乘法总和：1200 + (70 * 50) = 4700

情况 2 - 取 40 和 50

乘法：40 * 50 = 2000

并将 (40 + 50)%100 = 90 放回

执行此操作后，列表变为：30, 90

乘法总和：2000 + (30 * 90) = 4700

比较这两种情况，我们发现乘法运算的最小和是 2000，出现在情况 2 中。

因此，输出为：2000。

方法 1

一种方法是递归地解决这个问题，我们可以将其分解成更小的部分并将结果组合起来以找到最佳解决方案。我们可以定义一个二维表 DP[iterator1][iterator2]，其中 iterator1 和 iterator2 表示我们正在考虑的范围内的数字的索引。DP 表将存储从 iterator1 到 iterator2 乘以数字的乘法运算的最小和。

为了忽略重叠的子问题，我们将首先对这种方法应用备忘录。

示例

下面给出该问题的动态规划方法 -

#include <bits/stdc++.h>
using namespace std;

long long DP[1000][1000];
long long mult_sum(  int nums[], int iterator, int iterator2){	
   long long sol = 0;
   for ( int i = iterator; i <= iterator2; i++ ){
      sol = (sol + nums[i]) % 100;
   }
   return sol;
}
long long solve(int nums[], int iterator, int iterator2){
   if (iterator == iterator2)
      return 0;
   if (DP[iterator][iterator2] != -1)
      return DP[iterator][iterator2];
      DP[iterator][iterator2] = INT_MAX;
   for (int k = iterator; k < iterator2; k++){
      DP[iterator][iterator2] = min(DP[iterator][iterator2], (solve(nums, iterator, k) +	solve(nums, k + 1, iterator2) +	(mult_sum(nums, iterator, k) * mult_sum(nums, k + 1, iterator2))));
   }
   return DP[iterator][iterator2];
}
int main() {
   int nums[] = { 30, 40, 50 };
   int n = sizeof(nums)/sizeof(nums[0]);
   for (int iterator = 0; iterator <= n ; iterator++)
      for (int iterator2 = 0; iterator2 <= n ; iterator2++)
         DP[iterator][iterator2] = -1;
      cout << "The sum of multiplication of the numbers according to the definition given in the problem is " << solve(nums, 0, n - 1) << endl;
   return 0;
}

输出

The sum of multiplication of the numbers according to the definition given in the problem is 4700

方法 2

众所周知，动态规划的备忘录方法需要额外的堆栈空间来执行，因此为了减少这种空间复杂度，我们可以自顶向下地应用相同的方法，即表格法。

示例

上面讨论的相同问题的表格法如下 -

#include <bits/stdc++.h>
using namespace std;
long long mult_sum(int nums[], int iterator, int iterator2){	
   long long sol = 0;
   for (int it = iterator; it <= iterator2; it++){
      sol = (sol + nums[it]) % 100;
   }
   return sol;
}
long long min_sum_mult(int nums[], int n){
   long long store_dp[n][n];
   for (int iterator1 = 0; iterator1 < n; iterator1++) {
      for (int iterator2 = 0; iterator2 < n; iterator2++) {
         store_dp[iterator1][iterator2] = 0;
      }
   }
   for (int iterator1 = 2; iterator1 <= n; iterator1++) {
      for (int iterator2 = 0; iterator2 < n - iterator1 + 1; iterator2++) {
         int j = iterator2 + iterator1 - 1;
         store_dp[iterator2][j] = INT_MAX;
         for (int iterator3 = iterator2; iterator3 < j; iterator3++) {
            store_dp[iterator2][j] = min(store_dp[iterator2][j], (store_dp[iterator2][iterator3] +	store_dp[iterator3 + 1][j] +	(mult_sum(nums, iterator2, iterator3) * mult_sum(nums, iterator3 + 1, j))));
         }
      }
   }
   return store_dp[0][n - 1];
}
int main(){
   int nums[] = { 30, 40, 50 };
   int n = sizeof(nums)/sizeof(nums[0]);
   cout <<"The sum of multiplication of the numbers according to the definition given in the problem is "<< min_sum_mult(nums, n) << endl;
   return 0;
}

输出

The sum of multiplication of the numbers according to the definition given in the problem is 4700