[LeetCode] 343. Integer Break

 Problem : https://leetcode.com/problems/integer-break/

For each number i,  it can be broken into at least  j,  (i-j).  j = [1 ... i -1]

Let DP[i] = maximum product of number i when i be broken into at least 2 integers.

DP[i] = Max( j * (i-j),  j * DP[i-j] ),    j = [ 1 ... i - 1 ]

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [1] * (n+1)
        
        for i in range(3, n+1):
            for j in range(1, i):
                dp[i] = max(dp[i], max(j* (i-j),  j *dp[i-j]))
        
        return dp[n]

Another memorization approach:

class Solution {
    int[] memo;
    
    public int integerBreak(int n) {
        memo = new int[n+1];
        memo[1] = 1;
        
        return helper(n);
    }
    
    int helper(int n) {
        if (memo[n] != 0) {
            return memo[n];
        }
        
        for (int x = 1; x <= n / 2; x++) {
            
            // i.e. For number 3,  helper(3) = 1 * 2 = 2. 
            // 3 > helper(3).  we need to use 3 instead of helper(3) to get the larger product.
            memo[n] = Math.max(memo[n], Math.max(x, helper(x)) * Math.max(n-x, helper(n-x)));
        } 
        
        return memo[n];
    }
}

Edited on 11/26/2021. Update the top-down solution.