0️⃣python数据结构与算法学习路线
学习内容:
- 基本算法:枚举、排序、搜索、递归、分治、优先搜索、贪心、双指针、动态规划等…
- 数据结构:字符串(string)、列表(list)、元组(tuple)、字典(dictionary)、集合(set)、数组、队列、栈、树、图、堆等…
题目:
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
你可以认为每种硬币的数量是无限的。
输入输出:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
解题思路:
算法实现:
class Solution(object):
def coinChange(self, coins, amount):
dp=[float('inf')] * (amount+1)
dp[0] = 0 # 没想起来
for i in coins:
for j in range(i,amount+1):
dp[j]=min(dp[j],dp[j-i]+1) # 返回的是最小数量
return dp[-1] if dp[amount] != float('inf') else -1
出现问题:
- 用 for j in range(i, amount + 1):
替代:if j<i:
break - 初始化的时候要记得 dp[0]=0
- if dp[amount] != float(‘inf’) else -1,如果没有任何一种硬币组合能组成总金额,返回 -1。