✅C++✅||🕉️Apni-Bhasha-Mein||👍Seedhi-Baat-No-Bakwaas👌||DP😍 |Interview Prep👨‍💻🔥
Intuition & Approach\n- Explained in the code\n\n# Code\n\nclass Solution\n{\n   \tLOGIC\n\n   \tKARNA KYA HAIN\u2753\n   \t1. Integer "n" diya hain isko sum of
# Intuition & Approach\n- Explained in the code\n\n# Code\n```\nclass Solution\n{\n   \tLOGIC\n\n   \tKARNA KYA HAIN\u2753\n   \t1. Integer "n" diya hain isko sum of "k positive integers" mein todna\n   \thain.\n   \t2. k should always be ">=2".Matlab->Jyada se jyada numbers mein break karo.\n   \t3. Jo bhi k number ke sets banenge unme se max product wala set lena hain.\n\n   \tINTUITION &APPROACH\n   \t1. Ab apne ko itna to samajh aa raha hain ki "n ko bahut saare different\n   \tsets mein toda ja sakta hain".\n   \t2. Hame lekin max prod wala hi set lena hain.\n   \t3. So we have "many choices" to make sets.\n   \t4. Jahan yeh "choice shabd aagaya" wahan lagega "Recusion".\n   \t5. Ab Recurrence Relation\u2753\n   \t- Maximize karna hain to matlab har recursion mein "max" return karenge.\n   \t- Ab har num jo "<=n/2" hoga usse n ko break karenge .\n   \t- Why n/2\u2753Kyoki we have to make sure ki "jyada se jyada k value ho".\n   \t- Observation ke hisab se jitne jyada numbers mein breaked utna bada prod.\n   \t- Agar ">n/2" hoga to bade bade num mein break karna padega isse k ki val\n   \tchoti ho jayegi.\n   \t- "BASE-CASE":n==1->return 1\n   \t- So loop lagega "1 to n/2" tak ka aur har i ke liye max nikalenge. So,\n   \t"res=max(res,i* Recursion(n-i))"\n   \tWhere "Recursion(n-i)" means the max product for n-i value.\n   \t6. Ab kaafi overlapping problems hongi so to resolve this we will use DP.\n   \t7. RECURSION -> MEMOIZATION -> TABULATION\n   \t8. Memoization Steps\u2753\n   \t- See what parameter is changing decide the dp dimension .->Here only 1\n   \tparam is changing so "1D array".\n   \t- In recurrence relation store the max val in dp[n]\n   \t- Check if any dp[x] has been previously solved.\n   \t9. Tabulation Steps\n   \t- Replace Recurrence function with dp[]\n   \t- Declare base case in dp array.\n   \t- The recursion loop will be replaced by for loop.\n   \t "Meaning of dp[i]"\u2753-> It denotes the max product for digits in which\n   \tthe num i is divided.\n//==============================================================================================================================\n    public:\n         //MEMOIZATION    \n        int Memoization(int n, vector<int> &dp)\n        {\n            if (n == 1) return 1;\n           \t//BASE CASE\n            if (dp[n] != -1) return dp[n];\n           \t//Already solved\n            int ans = n;\n           \t//Could be INT_MIN also\n            for (int i = 1; i <= n / 2; i++)\n            {\n                ans = max(ans, i* Memoization(n - i, dp));\n               \t//Finding max among sets\n            }\n            return dp[n] = ans;\n           \t//Storing the max val\n        }\n    int integerBreak(int n)\n    {\n        if (n < 4) return n - 1;\n       \t//Precalculated\n        vector<int> dp(n + 1, -1);\n       \t//As only one param is changing\n        return Memoization(n, dp);\n    }\n\n   \t//TABULATION\n    int integerBreak(int n)\n    {\n        if (n < 4) return n - 1;\n        vector<int> dp(n + 1, 0);\n        dp[0] = 1;\n        dp[1] = 1;\n       \t//BASE cases\n        for (int num = 1; num <= n; num++)\n        {\n           \t//Iterating for num 1 to n\n            for (int div = 1; div <= num; div++)\n           \t//Calculating max prod for every num\n            {\n                dp[num] = max(dp[num], div *dp[num - div]);\n            }\n        }\n        return dp[n];\n    }\n};\n```\n# Complexity\n- Time complexity:$O(N^2)$\n\n- Space complexity:$O(N)$\n\nIf you *like* \uD83D\uDC4D this solution do *upvote* \u2B06\uFE0F and if there is any *improvement or suggestion* do mention it in the *comment* section \uD83D\uDE0A.\n\n<p align="center">\n<img src="https://assets.leetcode.com/users/images/1b604300-df68-46aa-a267-71f38463bb89_1684820402.7869222.jpeg" width=\'350\' alt="Upvote Image">\n</p>
['Math', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']