hello-algo/codes/python/chapter_dynamic_programming/coin_change_ii.py
Yudong Jin a005c6ebd3
Some improvements (#1073)
* Update avatar's link in the landing page

* Bug fixes

* Move assets folder from overrides to docs

* Reduce figures' corner radius

* Update copyright

* Update header image

* Krahets -> krahets

* Update the landing page
2024-02-07 22:21:18 +08:00

58 lines
1.6 KiB
Python
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

"""
File: coin_change_ii.py
Created Time: 2023-07-10
Author: krahets (krahets@163.com)
"""
def coin_change_ii_dp(coins: list[int], amt: int) -> int:
"""零钱兑换 II动态规划"""
n = len(coins)
# 初始化 dp 表
dp = [[0] * (amt + 1) for _ in range(n + 1)]
# 初始化首列
for i in range(n + 1):
dp[i][0] = 1
# 状态转移
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] = dp[i - 1][a] + dp[i][a - coins[i - 1]]
return dp[n][amt]
def coin_change_ii_dp_comp(coins: list[int], amt: int) -> int:
"""零钱兑换 II空间优化后的动态规划"""
n = len(coins)
# 初始化 dp 表
dp = [0] * (amt + 1)
dp[0] = 1
# 状态转移
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] = dp[a] + dp[a - coins[i - 1]]
return dp[amt]
"""Driver Code"""
if __name__ == "__main__":
coins = [1, 2, 5]
amt = 5
# 动态规划
res = coin_change_ii_dp(coins, amt)
print(f"凑出目标金额的硬币组合数量为 {res}")
# 空间优化后的动态规划
res = coin_change_ii_dp_comp(coins, amt)
print(f"凑出目标金额的硬币组合数量为 {res}")