# DP solution

• You can think of it as a tree and for each node you want to get the max value of its children , for example if n = 4 , 4 can be reached by 4-1 => check (3) solution * 1 or 4-2 => check(2) solution * 2 , for 3 -> 3 can be reached by 3-1 => 2 -> and 2 can be reached by 2 - 1 => 1 and we can say state of [1] will be 0 as base case, So state[2] will equal the maximum between dividing 2 to (1+1) or return 2 it self so state[2] = 2 , returning to state of 3 which will be the maximum between state[2] * 1 which is 2*1 or returning 3 it self so state[3] = 3 returning back to state[4] = state[3] * 1 and then try (2) solution * 2 we will find that we already solved state[2] so state[4] = max(state[3]*1,state[2]*2) returning 4

``````public class Solution {
public int solve(int n,int m,int state[]){
if(state[n] != -1)
return state[n];
int mx = -1;
for(int i = 1;i <= n/2;i++){
mx = Math.max(mx,solve(n-i,m,state)*i);
}
state[n] = mx;
if(n !=  m)
state[n] = Math.max(mx,n);
return state[n];
}
public int integerBreak(int n) {
int state[] = new int [n+1];
for(int i = 2;i < n+1;i++)
state[i] = -1;
state[0] = 0;
state[1] = 1;
if(n == 1)
return 0;
return solve(n,n,state);
}
}
``````

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