# AC solution using dynamic programming (no math), Python

• Note: I have also figured out a more efficient and simple backtracking algorithm with only 99ms in Python. Please check backtracking solution, where C++ and Python implementions are provided.

We test every possible `(m,n)` such that `a=m*n`. Then we get a solution `s` by concatenating `m` and `n`. However, `m` and `n` may themselves have multiple digits, which require further factorization. Therefore, a recursive method is used. After we get all the possible `s`, return the minimum one.

Note that in this recursive tree, we may encounter the same number for factorization. Therefore, a memoization trick is adopted to form a dynamic programming method.

``````class Solution(object):

def smallestFactorization(self, a):
"""
:type a: int
:rtype: int
"""
self.memory = {} # memory[k] is the Minimum Factorization of k
return self.dp(a)

def dp(self, k):
if k < 10:
return k
if k in self.memory:
return self.memory[k]
# here we test every possible factorization of k into k = m * n
# and find the minumum integer composed of m and n if any
s = int(math.sqrt(k))
factorizations = []
for m in range(s, 1, -1):
if k % m == 0:
n = k // m
left = self.dp(m)
right = self.dp(n)
if left != 0 and right != 0:    # only m and n both have answers
d = 0   # find the number of digits of right
t = right
while t > 0:
d += 1
t = t // 10
r = left * 10 ** d + right # for example, 123 and 247 => 123247
if r <= 2**31 - 1: # fit in 32-bit signed integer
factorizations.append(r)
if factorizations:  # if we have found any legal solution
self.memory[k] = min(factorizations)
else:
self.memory[k] = 0
return self.memory[k]``````

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