"""

File: coin_change.py

Created Time: 2023-07-10

"""

def coin_change_dp(coins: list[int], amt: int) -> int:

"""零钱兑换：动态规划"""

n = len(coins)

MAX = amt + 1

# 初始化 dp 表

dp = [[0] * (amt + 1) for _ in range(n + 1)]

# 状态转移：首行首列

for a in range(1, amt + 1):

dp[0][a] = MAX

# 状态转移：其余行列

for i in range(1, n + 1):

for a in range(1, amt + 1):

if coins[i - 1] > a:

# 若超过背包容量，则不选硬币 i

dp[i][a] = dp[i - 1][a]

else:

# 不选和选硬币 i 这两种方案的较小值

dp[i][a] = min(dp[i - 1][a], dp[i][a - coins[i - 1]] + 1)

return dp[n][amt] if dp[n][amt] != MAX else -1

def coin_change_dp_comp(coins: list[int], amt: int) -> int:

"""零钱兑换：空间优化后的动态规划"""

n = len(coins)

MAX = amt + 1

# 初始化 dp 表

dp = [MAX] * (amt + 1)

dp[0] = 0

# 状态转移

for i in range(1, n + 1):

# 正序遍历

for a in range(1, amt + 1):

if coins[i - 1] > a:

# 若超过背包容量，则不选硬币 i

dp[a] = dp[a]

else:

# 不选和选硬币 i 这两种方案的较小值

dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)

return dp[amt] if dp[amt] != MAX else -1

"""Driver Code"""

if __name__ == "__main__":

coins = [1, 2, 5]

amt = 4

# 动态规划

res = coin_change_dp(coins, amt)

print(f"凑到目标金额所需的最少硬币数量为 {res}")

# 空间优化后的动态规划

res = coin_change_dp_comp(coins, amt)

print(f"凑到目标金额所需的最少硬币数量为 {res}")