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