Python both backtracking and DP


  • 0

    My initial backtracking solution (not AC). Probably could've gotten it accepted if I added in memo.

        def coinChange(self, coins, amount):
            res = self.helper(coins, amount)
            if res == sys.maxint:
                return -1
            return res
            
        def helper(self, coins, amount):
            res = sys.maxint
            if amount == 0:
                return 0
            for denom in coins:
                if amount - denom >= 0:
                    res = min(res, 1 + self.helper(coins, amount-denom))
            return res
    

    Then developed a DP solution (iterative)

        def coinChange(self, coins, amount):
            dp = [sys.maxint for i in range(amount+1)]
            dp[0] = 0
            for i in range(amount+1):
                for denom in coins:
                    if i+denom < amount+1:
                        dp[i+denom] = min(dp[i+denom], dp[i] + 1)
            # no solution since its infinity
            if dp[-1] == sys.maxint:
                return -1
            return dp[-1]
    

Log in to reply
 

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