Java DP 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; j < i; j ++) {
dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
}
}
return dp[n];
}``````

• 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];
}
``````

}

• That's what I think

• ``````public int integerBreak(int n) {
if(n > 3) 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], j * dp[i-j]);
}
}
return dp[n];
}``````

• This post is deleted!

• Can you please explain the thought of this algorithm?

• Though your solution is correct, its complexity is O(n2)

• 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(n-i)==f(n-i)+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[i-j]*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[i-j]),(opt[j] * (i-j)),(opt[j]*opt[i-j]),(j*(i-j))
int t = Math.max(j,opt[j]) * Math.max((i-j) , opt[i-j]);
opt[i] = Math.max(opt[i], t);
}
}

return opt[n];
}``````

• Why can we assume dp[1] = 1?

• 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(i-j, dp[i-j]);
max = Math.Max(max, factor1 * factor2);
}
dp[i] = max;
}
return dp[n];
}
``````

• thank you for your solution

• This post is deleted!

• @cdai awesome

• Can someone explain this line?

Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));

I don't get what is being computed there.

• @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 was `if(n > 3) n++;`. I did notice that the values returned for `n` were at location `n+1` in my `dp` table. So, did you just do `n++` to return the correct values or is there some intuition behind this?

• @jaqenhgar said in Java DP solution:

if(n > 3) n++

why we will n++ here??

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.