मान लीजिए कि हमारे पास एक धनात्मक पूर्णांक n है, हमें इसे कम से कम दो धनात्मक संख्याओं के योग में तोड़ना है और उन पूर्णांकों के गुणनफल को अधिकतम करना है। हमें अधिकतम उत्पाद खोजना होगा जो हमें मिल सकता है। तो यदि संख्या 10 है, तो उत्तर 36 होगा, जैसे 10 =3 + 3 + 4, 3 * 3 * 4 =36
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक विधि हल () को परिभाषित करें, इसमें n, सरणी dp और ध्वज लगेगा
-
अगर n 0 है, तो 1 लौटाएं
-
अगर dp[n] -1 नहीं है, तो dp[n]
return लौटाएं -
अंत:=n – 1 जब ध्वज सेट हो, अन्यथा n
-
रिट:=0
-
क्योंकि मैं 1 से अंत तक की श्रेणी में हूं
-
रिट:=अधिकतम रिट और मैं * हल (एन - आई, डीपी, झूठा)
-
-
डीपी सेट करें [एन]:=रिट और रिटर्न
-
मुख्य विधि से, n + 1 आकार का एक सरणी dp बनाएं और इसे - 1 से भरें
-
वापसी हल (एन, डीपी)
उदाहरण (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