算法练习 Leetcode 力扣 518. Coin Change 2解法

作为lc322 coin change的follow up,leetcode标记为medium,而且acceptance rate为47%,高于coin change的34.2%。个人做下来觉得很难,比322要难。写出一个逻辑正确的解法还算OK,但是OJ会超时。

Python 版本 top down dfs + backtrace

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        cur_path = []
        paths = set()
        self.dfs(amount, coins, cur_path, paths)
        return len(paths)
        
    def dfs(self, amount, coins, cur_path, paths):
        if amount == 0:
            path = tuple(sorted(cur_path))
            paths.add(path)
            return
        if amount < 0:
            return
        for coin in coins:
            cur_path.append(coin)
            self.dfs(amount - coin, coins, cur_path, paths)
            del cur_path[-1]
        

Python 版本 bottom up dp

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        dp = [None] * (amount + 1)
        dp[0] = set()
        dp[0].add(())
        for i in range(1, amount + 1):
            combos = set()
            for coin in coins:
                rest = i - coin
                if rest >= 0 and dp[rest] is not None:
                    for rest_combo in dp[rest]:
                        combo = tuple(sorted(rest_combo + (coin,)))
                        combos.add(combo)
            if len(combos) > 0:
                dp[i] = combos
                
        return len(dp[amount]) if dp[amount] is not None else 0 

以上两种都超时。

实在想不到能过OJ的算法,以下dp算法也是我从网上大神们那学到了。盯着看了2天才算想明白了其中道理。写得非常简短。

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        dp = [1] + [0] * amount
        for coin in coins:
            for i in xrange(amount - coin + 1):
                if dp[i]:
                    dp[i + coin] += dp[i]
        return dp[amount]

Leave a Comment

Your email address will not be published.