LeetCode 322. Coin Change Python 动态规划/BFS解法
LeetCode 322. Coin Change Python 动态规划/BFS解法
大鹅
发布于 2021-06-15 15:30:23
发布于 2021-06-15 15:30:23
题目描述
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.You may assume that you have an infinite number of each kind of coin.
Example 1: coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1) Example 2: coins = [2], amount = 3 return -1.
Brute Force暴力求法(超时)
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
min_count = 9999
coins.sort(reverse=True)
length = len(coins)
if length == 1 and amount % coins[0] != 0:
return -1
elif amount % coins[0] == 0:
return int(amount / coins[0])
count_list = [0] * length
i = 0
while amount >= 0:
count_list[i] = int(amount / coins[i])
amount -= count_list[i] * coins[i]
i += 1
print(i, amount, count_list)
if amount == 0:
temp_sum = sum(count_list)
if temp_sum < min_count:
min_count = temp_sum
if i >= length:
j = i - 2
while j > 0 and count_list[j] == 0:
j -= 1
if j == 0 and count_list[j] <= 0:
break
if j >= length - 1:
return -1
else:
count_list[j] -= 1
amount += coins[j]
i = j + 1
for k in range(i, length):
if count_list[k] != 0:
amount += count_list[k] * coins[k]
count_list[k] = 0
if min_count == 9999:
return -1
else:
return min_countDP动态规划#1(超时)
基本思路：用dp存储硬币数量，dp[i] 表示凑齐钱数 i 需要的最少硬币数，那么凑齐钱数 amount 最少硬币数为：固定钱数为 coins[j] 一枚硬币，另外的钱数为 amount - coins[j] 它的数量为dp[amount - coins[j]]，j 从0遍历到coins.length - 1：
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [0]
length = len(coins)
for i in range(1, amount + 1):
dp += [9999]
for j in range(length):
if i >= coins[j] and dp[int(i - coins[j])] != 9999:
dp[i] = min(dp[i], dp[i - coins[j]] + 1)
if dp[amount] == 9999:
return -1
return dp[amount]DP动态规划#2(优化)
dp[x + c] = min(dp[x] + 1, dp[x + c])
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [0] + [-1] * amount
for x in range(amount):
if dp[x] < 0:
continue
for c in coins:
if x + c > amount:
continue
if dp[x + c] < 0 or dp[x + c] > dp[x] + 1:
dp[x + c] = dp[x] + 1
return dp[amount]BFS广度优先搜索解法
将问题转化为求X轴0点到坐标点amount的最短距离（每次向前行进的合法距离为coin的面值）
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if amount == 0:
return 0
value1 = [0]
value2 = []
nc = 0
visited = [False]*(amount+1)
visited[0] = True
while value1:
nc += 1
for v in value1:
for coin in coins:
newval = v + coin
if newval == amount:
return nc
elif newval > amount:
continue
elif not visited[newval]:
visited[newval] = True
value2.append(newval)
value1, value2 = value2, []
return -1参考文献
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-01-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录