C++-এ ভাগ করে নেওয়া বা যেন আছে নেওয়া — যেটি থেকে সর্বোচ্চ মান পাওয়া যায়

একটি সংখ্যা N দেওয়া আছে। আমরা চাইব F(N) এর সর্বোচ্চ মান, যেখানে:

F(N) = max( N, F(N/2) + F(N/3) + F(N/4) + F(N/5) )

এই রিকারেন্স রিলেশন ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা হয়।

উদাহরণ

N = 8
F(8) = F(4)+F(2)+F(2)+F(1) = 4+2+2+1 = 9
সুতরাং F(8) = max(8, 9) = 9

অ্যালগরিদম

• DP অ্যারে F[0..N] তৈরি করুন।
• F[0]=0, F[1]=1।
• i=2 থেকে N পর্যন্ত: divVal = F[i/2]+F[i/3]+F[i/4]+F[i/5]। F[i] = max(i, divVal)।
• F[N] রিটার্ন করুন।

C++ প্রোগ্রাম

#include <iostream>
using namespace std;

int calcMaximumValue(int N) {
    int F[N+1];
    F[0] = 0; F[1] = 1;
    for (int i = 2; i <= N; i++) {
        int divVal = F[i/2] + F[i/3] + F[i/4] + F[i/5];
        F[i] = max(i, divVal);
    }
    return F[N];
}

int main() {
    int N = 8;
    cout << "Maximum value = " << calcMaximumValue(N);
    return 0;
}

আউটপুট: Maximum value with the choice of either dividing or considering as it is = 9