# Why do you need DP?

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

• This is a typical math problem, lots of us have come up with this...of course DP is a choice if you cannot think of the solution in a instant.

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