public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for(int i = 2; i <= n; i ++) {
for(int j = 1; j < i; j ++) {
dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i  j, dp[i  j])));
}
}
return dp[n];
}
Java DP solution

Got the same idea with you, and we can save half of the time by changing the inside loop
j < i to 2*j <= i.
public class Solution {
public int integerBreak(int n) { int[] dp = new int[n + 1]; dp[1] = 1; for(int i = 2; i <= n; i ++) { for(int j = 1; 2*j <= i; j ++) { dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i  j, dp[i  j]))); } } return dp[n]; }
}

Same idea as yours. Here is another way to simplify DP function.
public int integerBreak(int n) { // 1.Init except dp[n], since it cannot be itself and must break into two positive int[] maxProd = new int[n + 1]; for (int i = 1; i < n; i++) { maxProd[i] = i; } // 2.Compute max product for (int i = 2; i <= n; i++) { for (int j = 1; j <= i  j; j++) { // Note: only check j <= i  j maxProd[i] = Math.max(maxProd[i], maxProd[j] * maxProd[i  j]); } } return maxProd[n]; }

my 3ms c++ dp solution.
The second loop can be half. since f(i)+f(ni)==f(ni)+f(i)int integerBreak(int n) { if(n==2) return 1; if(n==3) return 2; vector<int> cache(n+1, 0); cache[2] = 2; cache[3] = 3; for(int i=4; i<=n; i++){ for(int j=2; j<=i>>1; j++){ cache[i] = max(cache[i], cache[ij]*cache[j]); } } return cache[n]; }

@jaqenhgar looks like your solution is not pure dp like original post, still rely on the math. Normally j should be dp[j] to maximize value.

@cdai Thanks for the idea. you can also compare i and dp[i] afterwards.
public class Solution { public int integerBreak(int n) { int[] dp = new int[n + 1]; for (int i = 2; i <= n; i++) { dp[i  1] = Math.max(i  1, dp[i  1]); for (int j = 1; 2 * j <= i; j++) { dp[i] = Math.max(dp[i], dp[j] * dp[i  j]); } } return dp[n]; } }

public int integerBreak(int n) { if(n == 0) return 0; if(n == 1  n == 2) return 1; int[] opt = new int[n+1]; opt[1] = 1; opt[2] = 1; opt[3] = 2; for(int i=1;i<n+1;i++){ for(int j=2;j * 2 <= i;j++){ // j <= i/2, because when j >=i/2 they are dulplicated // no cut on the left part, optimal cut on the right part; // optimal cut on the left part, no cut on the right part; // optimal cut on the left part, optimal cut on the right part; // no cut on the left part, no cut on the right part; // max of(j * opt[ij]),(opt[j] * (ij)),(opt[j]*opt[ij]),(j*(ij)) int t = Math.max(j,opt[j]) * Math.max((ij) , opt[ij]); opt[i] = Math.max(opt[i], t); } } return opt[n]; }

Clearly the pure math solution is better, but the DP solution is a little easier to understand, IMO  C#
public class Solution { public int IntegerBreak(int n) { int[] dp = new int[n+1]; dp[1] = 1; for (int i = 1; i <= n; i++) { int max = 1; for (int j = 1; j < i; j++) { int factor1 = Math.Max(j, dp[j]); int factor2 = Math.Max(ij, dp[ij]); max = Math.Max(max, factor1 * factor2); } dp[i] = max; } return dp[n]; }


@jaqenhgar said in Java DP solution:
if(n > 3) n++;
Could you please let us know the intuition behind this step?
I coded the solution which is almost same as yours. The only statement I was missing wasif(n > 3) n++;
. I did notice that the values returned forn
were at locationn+1
in mydp
table. So, did you just don++
to return the correct values or is there some intuition behind this?
