DP || [UNBOUNDED KNAPSACK] || [TOP-DOWN AND BOTTOM-UP] || [C++]
TOP DOWN DP - MEMOIZATION \n\nclass Solution {\npublic: \n    \n    int dp[60][60]; \n    \n    int integerBreak(int n) { \n        \n        vector<int> nums; 
**TOP DOWN DP - MEMOIZATION** \n```\nclass Solution {\npublic: \n    \n    int dp[60][60]; \n    \n    int integerBreak(int n) { \n        \n        vector<int> nums; \n        \n        for(int i = 1; i <= n/2; i++) { \n            nums.push_back(i);\n        } \n        \n        if (n % 2 != 0) { \n            nums.push_back((n/2) + 1);\n        }\n        \n        memset(dp, -1, sizeof(dp));\n        \n        return UKS(nums, n, nums.size());\n    } \n    \n    int UKS(vector<int> &nums, int W, int n) { \n        \n        if (W == 0) { \n            return 1;\n        }   \n        \n        else if (n == 0) { \n            return 0;\n        }\n        \n        else if (dp[n][W] != -1) { \n            return dp[n][W];\n        } \n        \n        else if (nums[n-1] > W) { \n            return dp[n][W] = UKS (nums, W, n-1);\n        }\n        \n        return dp[n][W] = max(nums[n-1] * UKS(nums, W - nums[n-1], n), UKS(nums, W, n-1));\n    }\n};\n``` \n\n**BOTTOM-UP TABULATION** \n\n```\nclass Solution {\npublic: \n    \n    int dp[60][60]; \n    \n    int integerBreak(int n) { \n        \n        vector<int> nums; \n        \n        for(int i = 1; i <= n/2; i++) { \n            nums.push_back(i);\n        } \n        \n        if (n % 2 != 0) { \n            nums.push_back((n/2) + 1);\n        }\n        \n        int s = nums.size(); \n        \n        int dp[s+1][n+1]; \n        \n        for (int i = 0; i <= s; i++) { \n            \n            for (int j = 0; j <= n; j++) {  \n                \n                if (i == 0) { \n                    dp[i][j] = 0;\n                }  \n                \n                else if (j == 0) { \n                    dp[i][j] = 1;\n                }\n                \n                else if (nums[i-1] <= j) { \n                    dp[i][j] = max(nums[i-1] * dp[i][j-nums[i-1]], dp[i-1][j]);\n                } \n                \n                else { \n                    dp[i][j] = dp[i-1][j];\n                }\n            }\n        }\n        \n        return dp[s][n];\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C', 'C++']