প্রতিটি তিনটি ক্রমাগত উপাদান থেকে কমপক্ষে একটি নেওয়া হলে ন্যূনতম যোগফল বের করা 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] সমাধানের অংশ এবং শেষে বেছে নেওয়া উপাদান। তাহলে আমাদের ফলাফল হবে min(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