সমস্যা বিবরণ
N মিটার লম্বা একটি রস്സি দেওয়া থাকলে, এটিকে পূর্ণসংখ্যা দৈর্ঘ্যের টুকরোতে কাটতে হবে যাতে টুকরোগুলোর গুণফল সর্বোচ্চ হয়। কমপক্ষে এক কাট করতে হবে।
সমাধানের পদ্ধতি (Recursive DP)
- বেস কেস: n=0 বা 1 → 0 (কাট করা যায় না)।
- প্রতিটি i = 1 থেকে n-1 এর জন্য:
- অপশন ১: i এবং (n-i) দুটো টুকরো → গুণফল = i × (n-i)
- অপশন ২: i এবং (n-i)-কে আরও কাটা → গুণফল = i × maxProd(n-i)
- সর্বোচ্চ মান রিটার্ন করুন।
নোট: এটি রিকার্সিভ এবং এক্সপোনেনশিয়াল সময় নেয়। DP মেমোইজেশন বা বটম-আপ দিয়ে O(n²) করা যায়। গাণিতিকভাবে, ৩ দিয়ে ভাগ করলে সর্বোচ্চ গুণফল পাওয়া যায় (Integer Break problem)।
C++ কোড উদাহরণ (রিকার্সিভ)
#include <iostream>
using namespace std;
int max(int a, int b) { return (a > b) ? a : b; }
int max(int a, int b, int c) { return max(a, max(b, c)); }
int maxProd(int n) {
if (n == 0 || n == 1) return 0;
int max_val = 0;
for (int i = 1; i < n; i++)
max_val = max(max_val, i * (n - i), maxProd(n - i) * i);
return max_val;
}
int main() {
cout << "Maximum Product is " << maxProd(10);
return 0;
}
আউটপুট
Maximum Product is 36
ব্যাখ্যা
10 = 3 + 3 + 4 → গুণফল = 3 × 3 × 4 = 36
জটিলতা
- রিকার্সিভ: O(2ⁿ)
- DP (মেমোইজেশন): O(n²)
- গাণিতিক (O(1)): ৩ দিয়ে ভাগ করুন, বাকি ১ হলে ৪×৪, বাকি ২ হলে ৩×৩×২
