在 C++ 中查找最小和，使得每三个连续元素中至少取一个

假设我们有一个包含 n 个元素的数组。任务是从数组中找到元素的最小和，条件是必须从数组中每三个连续元素中至少选择一个元素。例如，如果数组是 [1, 2, 3, 6, 7, 1]，则输出为 4。如果我们选择 3 和 1，则 (3 + 1 = 4)。因此，有一些连续元素的子数组，例如 [1, 2, 3]、[2, 3, 6]、[3, 6, 7]、[6, 7, 1]，我们从每个子数组中选择了一个元素。

假设 sum(i) 返回最小可能的和，其中 arr[i] 是解决方案的一部分且是最后选择的元素。那么我们的结果是 sum(i – 1)、sum(i – 2)、sum(i – 3) 的最小值。我们可以看到这存在重叠子问题，因此我们可以使用动态规划方法来解决这个问题。

示例

 在线演示

#include <iostream>
using namespace std;
int minOfThree(int a, int b, int c) {
   return min(min(a, b), c);
}
int getMinSum(int arr[], int n) {
   int sum[n];
   sum[0] = arr[0];
   sum[1] = arr[1];
   sum[2] = arr[2];
   for (int i=3; i<n; i++)
   sum[i] = arr[i] + minOfThree(sum[i-3], sum[i-2], sum[i-1]);
   return minOfThree(sum[n-1], sum[n-2], sum[n-3]);
}
int main() {
   int arr[] = {1, 2, 3, 20, 2, 10, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Minimum sum is: " << getMinSum(arr, n);
}

输出

Minimum sum is: 4

更新于：2019-12-18

296 次浏览

开启你的 职业生涯

完成课程获得认证

开始学习
广告