ধরুন আমাদের একটি ধনাত্মক পূর্ণসংখ্যা n আছে, আমাদের এটিকে কমপক্ষে দুটি ধনাত্মক সংখ্যার যোগফলের মধ্যে ভাঙতে হবে এবং সেই পূর্ণসংখ্যাগুলির গুণফলকে সর্বাধিক করতে হবে। আমরা পেতে পারি সর্বোচ্চ পণ্য খুঁজে বের করতে হবে. সুতরাং সংখ্যাটি 10 হলে উত্তর হবে 36, যেমন 10 =3 + 3 + 4, 3 * 3 * 4 =36
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি পদ্ধতি সংজ্ঞায়িত করুন সমাধান(), এটি n, অ্যারে ডিপি এবং পতাকা লাগবে
-
যদি n 0 হয়, তাহলে 1 ফেরত দিন
-
যদি dp[n] -1 না হয়, তাহলে dp[n>
ফেরত দিন -
end :=n – 1 যখন পতাকা সেট করা হয়, অন্যথায় n
-
ret :=0
-
আমি পরিসীমা 1 থেকে শেষের জন্য
-
ret :=ret এবং i* সমাধানের সর্বোচ্চ (n – i, dp, false)
-
-
সেট করুন dp[n] :=রিটার্ন এবং রিটার্ন
-
প্রধান পদ্ধতি থেকে, n + 1 আকারের একটি অ্যারে dp তৈরি করুন এবং এটি – 1 দিয়ে পূরণ করুন
-
রিটার্ন সল্ভ(n, dp)
উদাহরণ (C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(int n, vector <int>& dp, bool flag = true){
if(n == 0) return 1;
if(dp[n] != -1) return dp[n];
int end = flag? n - 1: n;
int ret = 0;
for(int i = 1; i <= end; i++){
ret = max(ret, i * solve(n - i, dp, false));
}
return dp[n] = ret;
}
int integerBreak(int n) {
vector <int>dp(n + 1, -1);
return solve(n, dp);
}
};
main(){
Solution ob;
cout << (ob.integerBreak(10));
} ইনপুট
10
আউটপুট
36
