Recursion and DP | Java
1) Recursion\nThe idea is that at every value, we can loop from 1 to n-1 for the first value (a). The remain value (b) has two options:\n- Keep the same, which 
1) Recursion\nThe idea is that at every value, we can loop from 1 to n-1 for the first value (**a**). The remain value (**b**) has two options:\n- Keep the same, which means the product will be a * b\n- Or broken down, which means the product is: a * max(integerBreak(b))\n\nWe also want to cache the result using **n** as key.\n\n```java\nclass Solution {\n    Map<Integer, Integer> map = new HashMap<>();\n    \n    public int integerBreak(int n) {\n        if (map.containsKey(n)) return map.get(n);\n        \n        int res = Integer.MIN_VALUE;\n        if (n == 1) {\n            return 1;\n        } \n        \n        for(int i = 1; i <= n / 2; i++) {\n            res = Math.max(res, i * Math.max(n-i, integerBreak(n-i)));\n        }\n        \n        map.put(n, res);\n        return map.get(n);\n    }\n}\n```\n\n2) Similar to the recursion, we just use table to cache the value for dp\n```java\nclass Solution {\n    public int integerBreak(int n) {\n        if (n == 0) return 0; \n        if (n == 1) return 1;\n        \n        int[] dp = new int[n+1];\n        \n        dp[1] = 1;\n        \n        for(int i = 2; i <= n; i++) {\n            for(int j = 1; j <= i / 2; j++) {\n                dp[i] = Math.max(dp[i], j * Math.max(i-j, dp[i-j]));\n            }\n        }\n        \n        return dp[n];\n    }\n}\n```\n\nNote: for both methods, we only want to loop up to **n/2** since the values are mirrored. IE: 5 = 2 + 3 = 3 + 2
['Dynamic Programming', 'Recursion', 'Java']