There's a pattern associate with this problem, as you may observe:

4 = 2 + 2

5 = 2 + 3

6 = 3 + 3

7 = (3) + 2 + 2

8 = (3) + 2 + 3

9 = (3) + 3 + 3

10 = (3 + 3) + 2 + 2

11 = (3 + 3) + 2 + 3

12 = (3 + 3) + 3 + 3

13 = (3 + 3 + 3) + 2 + 2

See? So I came up with a solution without using DP, I think it is O(logn) given that pow is O(logn). But since integer is 32-bit which is fixed, you may argue it is O(1).

```
int integerBreak(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
int extraThrees = (n-4)/3;
int index = (n-4)%3;
return power(3, extraThrees) * (index==0?4:(index==1?6:9));
}
int power(int a, int n) {
if (n == 0) return 1;
if (n == 1) return a;
int subres = power(a,n/2);
if (n%2 == 1) return subres * subres * a;
else return subres * subres;
}
```