public int integerBreak(int n) {
int[] res = new int[n+1];
res[1] =1;
// For numbers from 2 to 6
for (int i = 2; i <= 6 && i <= n; i++){
res[i] = (int)i/2 * ( i  (int)i/2);
}
// For numbers larger than 6, apply DP.
for (int i = 7; i <= n; i++) {
res[i] = Math.max(res[i2] * 2, res[i3] * 3);
}
return res[n];
}
Java 0ms DP Solution



@kireeti2 In order to get the maximum, we need to break the integer into as many 2 or 3 as we can. For example, for 15, the max comes from 3+3+3+3+3; for 16, it will be 3+3+3+3+2+2, etc.

@jguo11 said in Java 0ms DP Solution:
yes i got that ..but why would that work. any specific reason ..or just an observation?

@kireeti2 For now, those are just my observation and there must be some math deductions can be done to prove it.

@kireeti2 The key for this problem is that we need to break the number to
2
s(or4
s), and3
s.
First we need to know a fact that,if a,b > 3, ab <= 1, then a*b>=a+b
.So,
if n = a + b, a = a1+a2, b=b1+b2
, we should break n toa1+a2+b1+b2, a1a2<1 and b1b2<1
instead ofa + b
, becausea1*a2>a, b1*b2>b
. However, we shall stop when we get a3
or2
, so what we shall do is to find the list of3
and2
.You may have noticed why the
4
appeared. 'Cause if we break4
, we get2+2
, and2+2 = 2*2
, so it's the same with the condition that we get two2
s.