Leetcode 322. Coin Change

1. Description

2. Solution

• Version 1

代码语言：javascript复制

class Solution:
    def coinChange(self, coins, amount):
        if amount == 0:
            return 0
        stat = [0] * (amount   1)
        for i in range(amount   1):
            for coin in coins:
                if i - coin > 0 and stat[i - coin] > 0:
                    if stat[i] > 0:
                        stat[i] = min(1   stat[i - coin], stat[i])
                    else:
                        stat[i] = 1   stat[i - coin]
                elif i - coin == 0:
                    stat[i] = 1

        return stat[amount] if stat[amount] > 0 else -1

• Version 2

代码语言：javascript复制

class Solution:
    def coinChange(self, coins, amount):
        if amount == 0:
            return 0
        stat = [0 if i not in coins else 1 for i in range(amount   1)]
        for i in range(amount   1):
            for coin in coins:
                if i - coin > 0 and stat[i - coin] > 0:
                    if stat[i] > 0:
                        stat[i] = min(1   stat[i - coin], stat[i])
                    else:
                        stat[i] = 1   stat[i - coin]

        return stat[amount] if stat[amount] > 0 else -1

Reference

1. https://leetcode.com/problems/coin-change/

version

0 人点赞