Share my 32ms 9 line Python code using DP with memoization


  • 0
    B
    class Solution(object):
        def integerReplacement(self, n):
            memo = {1 : 0}
            def helper(m):
                if m not in memo:
                    # From an odd number m, you must jump to (m - 1) / 2 or (m + 1) / 2 using two steps
                    memo[m] = helper(m // 2) + 1 if m % 2 == 0 else min(helper((m - 1) / 2), helper((m + 1) / 2)) + 2
                return memo[m]
            return helper(n)
    

    The idea is simple, if n is an even integer, then the minimum number of replacement is the number of n / 2 plus one; if n is an odd integer, then the minimum number of replacement is the smaller for n + 1 and n - 1 plus one.

    Here, memoization is used to save some space because some cases are never reached. e.g. helper(7)->helper(4)->helper(2)->helper(1), helper(7)->helper(3)->helper(2)->helper(1), helper(7)->helper(3)->helper(1). 5 is not called. The called numbers will be more sparse with larger n.


Log in to reply
 

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