在 C++ 中找出将整数数组合并为单个值的成本的程序

假设我们有一个包含 n 个正整数的数组 arr。我们还得到了一个整数 j。我们必须执行的任务是通过相加将 j 个数字合并为一个数字。合并的成本等于我们选择的 j 个数字的相加。我们必须找出这个合并操作的最小可能成本。

因此，如果输入类似于 arr = [2, 5, 6, 2, 3, 1, 3], j = 4，那么输出将是 31。

合并 2, 3, 1, 3 的成本等于 2 + 3 + 1 + 3 = 9。

合并操作后的数组变为 [2, 5, 6, 9]。第二次合并操作的成本等于 2 + 5 + 6 + 9 = 22。因此，合并操作的总成本变为 22 + 9 = 31。这是最小的合并成本。

示例

让我们看看以下实现以获得更好的理解 -

#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>& arr, int j) {
   int n = arr.size();
   if ((n - 1) % (j - 1) != 0) return -1;

   vector<int> temp(n + 1);
   for (int i = n - 1; i >= 0; i--) {
      temp[i] = arr[i] + temp[i + 1];
   }
   vector<vector<int>> dynArr(n, vector<int>(n));
   for (int k = j; k <= n; k++) {
      for (int le = 0, rg = k - 1; rg < n; le++, rg++) {
         dynArr[le][rg] = INT_MAX;
         for (int i = le; i < rg; i += j - 1) {
            dynArr[le][rg] = min(dynArr[le][rg], dynArr[le][i] + dynArr[i + 1][rg]);
         }
         if ((rg - le) % (j - 1) == 0) {
            dynArr[le][rg] += temp[le] - temp[rg + 1];
         }
      }
   }
   return dynArr[0][n - 1];
}

int main() {
vector<int> arr = {2, 5, 6, 2, 3, 1, 3};
cout<< solve(arr, 4) <<endl;
return 0;
}

输入

{2, 5, 6, 2, 3, 1, 3}, 4

31