ধরুন আমাদের 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) ন্যূনতম সম্ভাব্য যোগফল প্রদান করবে, যেখানে arr[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
