Leetcode Link: 剑指 Offer II 103. 最少的硬币数目 - 力扣（LeetCode）
题目
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
从暴力递归到动态规划
暴力递归
典型的从左到右的尝试模型，思路和代码都和零钱兑换几个问题比较相似
然而本题的问题变成了最小的隐硬币数量
所以我们需要知道如何”返回最小硬币的数量”，并且需要知道如何处理异常情况
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
res = self.process(coins, 0, amount)
return -1 if res==float('inf') else res
def process(self, coins, idx, rest):
### 尽量使用 == 来确定base case
### 实际上我们能够进一步简化，譬如 rest == 0时就可以直接返回了
if idx == len(coins) and rest == 0:
return 0
if idx == len(coins) and rest > 0:
return -1
# rest < 0 的我就不让进来了,所以不写这个base case
res = float('inf')
n = 0
while(rest-n*coins[idx]>=0):
tmp = self.process(coins, idx+1, rest-n*coins[idx])
if tmp != -1: # 异常情况不能和结果比较
res = min(res, tmp+n) # 记得加上当前使用的货币数量
n += 1
return res动态规划
比较简单，直接改就行， 但是依然超时，主要原因是while那里遇到amount很大但是面值很小的时候，会浪费大量时间
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# [idx, rest]
dp = [[0 for _ in range(amount+1)] for _ in range(len(coins)+1)]
# init
dp[len(coins)][0] = 0
for i in range(1, amount+1):
dp[len(coins)][i] = -1
for idx in range(len(coins)-1, -1, -1):
for rest in range(amount+1):
dp[idx][rest] = float('inf')
n = 0
while(rest-n*coins[idx]>=0):
tmp = dp[idx+1][rest-n*coins[idx]]
if tmp != -1: # 异常情况不能和结果比较
dp[idx][rest] = min(dp[idx][rest], tmp+n) # 记得加上当前使用的货币数量
n += 1
return -1 if dp[0][amount]== float('inf') else dp[0][amount]动态规划（状态压缩）
根据前面的代码画出空间位置依赖图
√依赖 (a+0, b+1, c+2, …) x 依赖 (b+0, c+1, d+3)…
所以，√ = min (x+1, a)
但是，我们需要处理异常值情况。
在上面的代码中，我们在base case中设置了异常为-1，而在一般case中，如果所有情况都为异常，则会返回的是 float('inf')，即在一般case中我们的异常为 float('inf')
在这个代码中，我们会直接比较左和下的格子，这样一定会把-1的异常值一直带着，所以这里是有问题的，我们需要将异常值全部改为flaot('inf')，并且修改部分代码逻辑
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# [idx, rest]
dp = [[0 for _ in range(amount+1)] for _ in range(len(coins)+1)]
# init
dp[len(coins)][0] = 0
for i in range(1, amount+1):
dp[len(coins)][i] = float('inf') # 异常情况
for idx in range(len(coins)-1, -1, -1):
for rest in range(amount+1):
if rest-coins[idx] >= 0:
dp[idx][rest] = min(dp[idx+1][rest], dp[idx][rest-coins[idx]]+1)
else:
dp[idx][rest] = dp[idx+1][rest]
return -1 if dp[0][amount]== float('inf') else dp[0][amount]