Integer Break - Teeeeeebag/LeetCode GitHub Wiki

public class Solution {
    //5 = 2*3, 1*4
    public int integerBreakImpl(int end, int[] dp){
        int res = Integer.MIN_VALUE;
        if (dp[end] > 0)
            return dp[end];
        for (int i=1; i<=end/2; ++i){
            res = Math.max(res, i*(end-i));
            if (i>=2){
                res = Math.max(res, integerBreakImpl(i, dp) * (end-i));
            }
            if (end - i >= 2){
                res = Math.max(res, integerBreakImpl(end-i, dp) *(i));
            }
            if (i>=2 && end-i >=2){
                res = Math.max(res, integerBreakImpl(end-i, dp) *integerBreakImpl(i, dp));
            }
        }
        dp[end] = res;
        return res;
    }
    public int integerBreak(int n){
        int[] dp = new int[n+1];
        return integerBreakImpl(n, dp);
    }   

}