算法練習 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.