This is the first time I try to share my solution so please be kind if you think it's not good. :)

I first came up with a recursive solution but it got TLE and I realized there were sub-solutions being repeatedly computed. And that's when DP comes into play.

Two things to be kept in mind:

- If
`a < 10`

, then it's already the optimal. Just return it. - Only need to consider factors from 2 to 9.

In the recursive version, try factors (call it `i`

) from 2 to 9.

Skip if it's not a factor (i.e. `a%i != 0`

) or if no solution exists for the subproblem `(a/i)`

(which we will recursively solve).

Keep these sub-answers in a list and the final answer is the minimum among these.

The DP solution is simply using a dictionary to memoize sub-solutions so that when you need it next time, you just do a lookup.

```
opt = {}
def smallestFactorization(a):
if a < 10:
return a
temp = []
for i in xrange(2, 10):
if a % i != 0:
continue
if (a/i) not in opt:
t = smallestFactorization(a/i)
opt[(a/i)] = t
t = opt[(a/i)]
if t == 0:
continue
temp.append(int(str(i)+str(t)))
ans = min(temp) if len(temp) > 0 else 0
if ans > 2**31:
return 0
return ans
```