3つの連続する要素ごとに1つがC++で取得されるような最小の合計を見つけます

n個の要素の配列があるとします。タスクは、配列から要素の最小合計を見つけることです。その配列内の3つの連続する要素ごとに少なくとも1つの要素1つの要素が選択されるようにします。したがって、配列が[1、2、3、6、7、1]のような場合。出力は4です。したがって、3と1を選択すると、（3 + 1 =4）になります。したがって、[1、2、3]、[2、3、6]、[3、6、7]、[6、7、1]のような連続する要素のサブ配列がいくつかあり、すべてのサブ配列から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