找到最小和，以便在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