# Python DP solution

• 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:

1. If `a < 10`, then it's already the optimal. Just return it.
2. 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
``````

• @franco3 Great solution!

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