C++ || Top-Down Dp || Easy To Understand
Approach:-\n\nIn dp helper function i have taken three arguments n, dp array and m\nIn each recursive call we will try with the product of all possible number f
**Approach:-**\n\nIn dp helper function i have taken three arguments n, dp array and m\nIn each recursive call we will try with the product of all possible number from 1 to n and check at which case we get maximum answer.\nAfter that if n!=m (m is the original number itself) then n itself may be the possible maximum product, so we have checked the max(ans,n) only when n is not equal to the original input number. \nKindly have a look into the code below for better understanding\n\n**Complexity:-**\n**Time :-** O(n^2)\n**Space :-** O(n)\n\n**Code:-**\n```\nclass Solution {\n    int helper(int n,vector<int> &dp,int m){\n        if(n==1){\n            return dp[n] = 1;\n        }\n        if(dp[n]!=-1){\n            return dp[n];\n        }\n        int ans = 1;\n        for(int i=1;i<=n;i++){\n            if(n-i>0){\n                ans = max(ans,(i*helper(n-i,dp,m)));\n            }\n        }\n        if(n!=m){\n            ans = max(ans,n);\n        }\n        return dp[n]=ans;\n    }\npublic:\n    int integerBreak(int n) {\n        vector<int> dp(n+1,-1);\n        return helper(n,dp,n);\n    }\n};\n```\n\nHope you liked it, thanks :)
['Dynamic Programming', 'Memoization']