न्यूनतम योग इस प्रकार ज्ञात कीजिए कि प्रत्येक तीन क्रमागत तत्वों में से एक को 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] जैसे लगातार तत्वों के कुछ उप-सरणी हैं, हमने प्रत्येक उप-सरणी से एक तत्व चुना है।

योग पर विचार करें (i) न्यूनतम संभव योग लौटाएगा, जहां गिरफ्तारी [i] समाधान का हिस्सा है और अंतिम चुना गया तत्व है। फिर हमारा परिणाम योग का न्यूनतम (i - 1), योग (i - 2), योग (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