न्यूनतम योग खोजें जैसे कि हर तीन लगातार तत्वों में से एक लिया जाए 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