leetcode IntegerBreak

import java.util.ArrayList;

public class IntegerBreak {
  /**
   * Integer Break
   * Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
   *
   * Example 1:
   *
   * Input: 2
   * Output: 1
   * Explanation: 2 = 1 + 1, 1 × 1 = 1.
   * Example 2:
   *
   * Input: 10
   * Output: 36
   * Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
   * Note: You may assume that n is not less than 2 and not larger than 58.
   */

  // this solution may couse time execeeding.
  public int integerBreak(int n) {
    ArrayList<Integer> t = new ArrayList<>();
    ArrayList<Integer> ans = new ArrayList<>();
    dfs(1, n-1, t, n, ans);
    int max = 0;
    for (int i: ans){
      max = Math.max(max, i);
    }
    return max;
  }
  public void dfs(int start, int end, ArrayList<Integer> t, int sum, ArrayList<Integer> last){
    if (sum == 0){
      int ans = 1;
      for (int num: t){
        ans *= num;
      }
      last.add(ans);
      return ;
    }
    if (sum < 0) return ;

    for (int i=start; i<=end; i++){
      t.add(i);
      dfs(start, end, t, sum-i, last);
      t.remove(t.size()-1);
    }
  }

  // math solution.
  public int intetBreakerII(int n){
    if (n == 1 || n == 2) return 1;
    int max = 0;
    for (int i=2; i<n; i++){
      max = Math.max(max, helper(n, i));
    }
    return max;
  }

  public int helper(int n, int i){
    // i: stands for there're i numbers that sums up to n, we want distribute numbers near equally to each number.
    int base = n/i;
    int left = n%i;
    int production = 1;
    for (int j=0; j<i; j++){
      if (left-- > 0){
        production *= (base + 1);
      }
      else{
        production *= base;
      }
    }
    return production;
  }

  // dp solution. dp[i] = max(j*dp[i-j]) for 1<= j<= i;
  public int intetBreakerIII(int n){
    int[] dp = new int[n];
    int max = 0;
    dp[1] = 1;
    dp[2] = 1;
    for (int i=2; i<=n; i++){
      for (int j=1; j<i; j++){
        max = Math.max(max, j*dp[i-j]);
      }
    }
    return max;
  }
}