Leetcode 322. Coin Change

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Coin Change

2. Solution

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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/
如果有收获,可以请我喝杯咖啡!