Python DP solution

  • 0

    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:
                if (a/i) not in opt:
                    t = smallestFactorization(a/i)
                    opt[(a/i)] = t
                t = opt[(a/i)]
                if t == 0:
            ans = min(temp) if len(temp) > 0 else 0
            if ans > 2**31:
                return 0
            return ans

  • 0

    @franco3 Great solution!

Log in to reply

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