CPP, JAVA Recursion -> Memoization (0 ms) -> bottom-up (0 ms)
This question is a classic rod cutting problem a subset of unbounded knapsack problem. \nThe only catch is that we are multiplying with idx as we need to maximi
This question is a classic rod cutting problem a subset of unbounded knapsack problem. \nThe only catch is that we are multiplying with idx as we need to maximise the product\nThe cpp solution got 0 ms while Java soln got 3 ms. \n\n-->Recursion(68 ms)\n```\nclass Solution {\npublic:\n    int helper(int n, int idx)\n    {\n       if(n == 0 or idx == 0) return 1;\n        \n       if(idx > n) return helper(n, idx - 1);\n      \n       return max((idx * helper(n - idx, idx)), helper(n , idx - 1));\n    }\n    \n    int integerBreak(int n)\n    {\n       return helper(n, n - 1);\n    }\n};\n```\n\nFor Java (49 ms) \n```\nclass Solution {\n    public int helper(int n, int idx)\n    {\n       if(n == 0 || idx == 0) return 1;\n        \n       if(idx > n) return helper(n, idx - 1);\n      \n       return Math.max((idx * helper(n - idx, idx)), helper(n , idx - 1));\n    }\n    \n    public int integerBreak(int n)\n    {\n        return helper(n, n - 1);\n    }\n}\n```\n\n--> Memoization(0 ms)\n```\nclass Solution {\npublic:\n    int dp[59][58];\n    \n    int helper(int n, int idx)\n    {\n       if(n == 0 or idx == 0) return 1;\n        \n       if(dp[n][idx] != -1) return dp[n][idx];\n        \n       if(idx > n) return dp[n][idx] = helper(n, idx - 1);\n      \n       return dp[n][idx] = max((idx * helper(n - idx, idx)), helper(n , idx - 1));\n    }\n    \n    int integerBreak(int n)\n    {\n        memset(dp, -1, sizeof dp);\n        \n        return helper(n, n - 1);\n    }\n};\n```\n\n--> bottom up approach(0 ms)\n```\nclass Solution {\npublic:\n\n    int integerBreak(int n)\n    {\n        vector<vector<int>> dp (n + 1, vector<int>(n, 1));\n        \n        for(int row = 1; row < n + 1; row++)\n        {\n            for(int col = 1; col < n; col++)\n            {\n                if(row >= col)\n                  dp[row][col] = max(col * dp[row - col][col], dp[row][col - 1]);\n                \n                else\n                    dp[row][col] = dp[row][col - 1];\n            }\n        }\n        \n        return dp[n][n - 1];      \n    }\n};\n```\n\nfor Java (3 ms)\n```\nclass Solution {\n    public int integerBreak(int n)\n    {\n        int dp[][] = new int[n + 1][n];\n        \n        for(int row = 0; row < n + 1; row++)\n        {\n            for(int col = 0; col < n; col++)\n            {\n                if(row == 0 || col == 0)\n                 dp[row][col] = 1;\n            }\n        }\n        \n        for(int row = 1; row < n + 1; row++)\n        {\n            for(int col = 1; col < n; col++)\n            {\n                if(row >= col)\n                  dp[row][col] = Math.max(col * dp[row - col][col], dp[row][col - 1]);\n                \n                else\n                    dp[row][col] = dp[row][col - 1];\n            }\n        }\n        \n        return dp[n][n - 1];      \n    }\n\t```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']