lc-343

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

• 2 <= n <= 58

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int integerBreak(int n) {
        if (n <= 1) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        return getRes(map, n);
    }

    private int getRes(Map<Integer, Integer> map, int n) {
        if (map.containsKey(n)) {
            return map.get(n);
        }

        if (n == 2 || n == 1) {
            map.put(n, 1);
            return 1;
        }

        int result = 0;

        for (int i = 1; i <= n / 2; i++) {
            int leftRes = getRes(map, i);
            int rightRes = getRes(map, n - i);
            int cur = leftRes * rightRes;
            if (i * (n - i) > cur) {
                cur = i * (n - i);
            }
            if (i * rightRes > cur) {
                cur = i * rightRes;
            }
            if (leftRes * (n - i) > cur) {
                cur = leftRes * (n - i);
            }
            if (cur > result) {
                result = cur;
            }
        }

        map.put(n, result);
        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)