✅C++ || Recursion->Memoization->Tabulation->SpaceOptimization
Extension of Unbounded Knapsack\n\n# Method - 1 [Recursion]\n\n\n\nT->O(>>2^n) && S->O(n) [Recursion Stack Space]\n \n\t class Solution {\n\tpublic:\n\t\tint f(
***Extension of Unbounded Knapsack***\n\n# Method - 1 [Recursion]\n\n![image](https://assets.leetcode.com/users/images/f5ffa5b9-b47a-474a-889f-ff3085b32c58_1661268384.0396595.png)\n\n**T->O(>>2^n) && S->O(n) [Recursion Stack Space]**\n \n\t class Solution {\n\tpublic:\n\t\tint f(int i,int sum){\n\t\t\tif(i==1) return 1; \n\t\t\tint notpick=f(i-1,sum);\n\t\t\tint pick=0;\n\t\t\tif(sum>=i) pick=i*f(i,sum-i);\n\t\t\treturn max(pick,notpick);\n\t\t}\n\n\t\tint integerBreak(int n){\n\t\t\treturn f(n-1,n);\n\t\t}\n\t}; \n\t\n![image](https://assets.leetcode.com/users/images/bc051183-4045-4935-9f04-67481e8677df_1661268798.458068.png)\n\n**T->O(n^2) && S->O(n^2) + O(n) [Recursion Stack Space]**\n\n\tclass Solution {\n\tpublic:\n\t\tint f(int i,int sum,vector<vector<int>>& dp){\n\t\t\tif(i==1) return 1; \n\t\t\tif(dp[i][sum]!=-1) return dp[i][sum];\n\t\t\tint notpick=f(i-1,sum,dp);\n\t\t\tint pick=0;\n\t\t\tif(sum>=i) pick=i*f(i,sum-i,dp);\n\t\t\treturn dp[i][sum]=max(pick,notpick);\n\t\t}\n\n\t\tint integerBreak(int n){\n\t\t\tvector<vector<int>> dp(n,vector<int>(n+1,-1));\n\t\t\treturn f(n-1,n,dp);\n\t\t}\n\t}; \n\n# Method - 3 [Tabulation]\n\n![image](https://assets.leetcode.com/users/images/1d426630-e039-49d8-b9f3-1d0c5d884d69_1661269238.3084671.png)\n\n**T->O(n^2) && S->O(n^2)**\n\n\tclass Solution {\n\tpublic:\n\t\tint integerBreak(int n){\n\t\t\tvector<vector<int>> dp(n,vector<int>(n+1,0));\n\t\t\tfor(int j=0;j<n+1;j++) dp[1][j]=1;\n\t\t\tfor(int i=2;i<n;i++){\n\t\t\t\tfor(int sum=0;sum<=n;sum++){\n\t\t\t\t\tint notpick=dp[i-1][sum];\n\t\t\t\t\tint pick=0;\n\t\t\t\t\tif(sum>=i) pick=i*dp[i][sum-i];\n\t\t\t\t\tdp[i][sum]=max(pick,notpick);\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn dp[n-1][n];\n\t\t}\n\t}; \n\t\n# Method - 4 [SpaceOptimization]\t\n![image](https://assets.leetcode.com/users/images/3662112e-7451-4735-a2a9-c7a4837dd840_1661269586.0845575.png)\n\n**T->O(n^2) && S->O(n)**\n\n\tclass Solution {\n\tpublic:\n\t\tint integerBreak(int n){\n\t\t\tvector<int> prev(n+1,1),curr(n+1,0);\n\t\t\tfor(int i=2;i<n;i++){\n\t\t\t\tfor(int sum=0;sum<=n;sum++){\n\t\t\t\t\tint notpick=prev[sum];\n\t\t\t\t\tint pick=0;\n\t\t\t\t\tif(sum>=i) pick=i*curr[sum-i];\n\t\t\t\t\tcurr[sum]=max(pick,notpick);\n\t\t\t\t}\n\t\t\t\tprev=curr;\n\t\t\t}\n\t\t\treturn prev[n];\n\t\t}\n\t}; \n\n
['Dynamic Programming', 'Backtracking', 'Recursion', 'Memoization', 'C', 'C++']