53 lines
1.7 KiB
Python
53 lines
1.7 KiB
Python
"""
|
||
动态规划的核心：
|
||
将大问题分解为多个小问题，通过解决一个个小问题，
|
||
并保存解决每个小问题时的状态最终解决大问题
|
||
|
||
动态规划实现找零：
|
||
1. 先看找零1元需要多少：1
|
||
2. 找零2元需要多少：两张1元
|
||
3. 找零3元需要多少：找零2元的结果+找零1元的结果
|
||
"""
|
||
|
||
|
||
# 动态规划找零
|
||
def dp_rec_mc1(changes: list[int], cash: int):
|
||
min_changes = [0 for _ in range(cash + 1)]
|
||
for i in range(1, cash + 1):
|
||
min_amount = i
|
||
for c in filter(lambda x: x <= i, changes):
|
||
temp_min_amount = 1 + min_changes[i - c]
|
||
if temp_min_amount < min_amount:
|
||
min_amount = temp_min_amount
|
||
|
||
min_changes[i] = min_amount
|
||
|
||
return min_changes[cash]
|
||
|
||
|
||
# 动态规划找零，并保存每一种找零所需的纸币情况
|
||
def dp_rec_mc2(changes: list[int], cash: int):
|
||
change_used: dict[int, dict[int, int]] = {}
|
||
min_amounts = [0 for _ in range(cash + 1)]
|
||
for i in range(1, cash + 1):
|
||
min_amount = i
|
||
changes_less_then_i = filter(lambda x: x <= i, changes)
|
||
for c in changes_less_then_i:
|
||
temp_min_amount = 1 + min_amounts[i - c]
|
||
if temp_min_amount < min_amount:
|
||
min_amount = temp_min_amount
|
||
if i - c > 0:
|
||
change_used[i] = change_used[i - c].copy()
|
||
if change_used[i].get(c):
|
||
change_used[i][c] += 1
|
||
else:
|
||
change_used[i][c] = 1
|
||
else:
|
||
change_used[i] = {c: 1}
|
||
|
||
min_amounts[i] = min_amount
|
||
if min_amount == i:
|
||
change_used[i] = {1: i}
|
||
return change_used[cash]
|
||
|