零钱兑换问题
def coinChange(coins, amount):
if amount == 0:
return 0
if len(coins) == 0:
return -1
if len(coins) ==1 and coins[0] > amount:
return -1
mem = [-1 for i in range(amount + 1)]
mem[0] = 0
for i in range(1, amount + 1):
cur_min = amount + 1
for c in coins:
if c <= i:
cur_min = mem[i - c] if mem[i - c] < cur_min else cur_min
mem[i] = cur_min + 1 if cur_min < amount + 1 else amount + 1
if mem[-1] == amount + 1:
return -1
else:
return mem[-1]
Processed:
0.013, SQL:
9
