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