DPL_1_A: Coin Changing Problem
ここから動的計画法の章
これまでにいくつか動的計画法の問題があったのでざっと復習しておこう
第11章か
だいぶ苦労してたな
c1、c2、・・・、cm円のコインでn円を支払うときの最小の枚数を求める
星は思考がふたつで実装がひとつ
それほどでもないはず
動的計画法を使わずに一度解いてみるのがいいかな
再帰で分割統治
ある種別のコインを1枚使った時と、そのコインを使わないときに分けて考える
from typing import Any, List, Optional
from sys import setrecursionlimit
def changes(amount: int, kind: int, coins: List[int]) -> int:
min_changes = 50001
def rec(a: int, k: int, changes: int) -> None:
nonlocal min_changes
if a == 0:
min_changes = min(min_changes, changes)
return
elif a < 0 or k < 0:
return
else:
rec(a - coins[k], k, changes + 1)
rec(a, k - 1, changes)
rec(amount, kind - 1, 0)
return min_changes
def main() -> None:
n, m = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]
setrecursionlimit(10000)
print(changes(n, m, c))
main()
Case #9でTLE
8つ正解したからロジックは大丈夫かな
rec
に@lru_cache()
つけてみたけどやっぱり#9でTLE
あんまり意味がない気はしていた
たぶん引数のchanges
を減らさないと
こんな感じかな
かえって短くなった
def changes(amount: int, kind: int, coins: List[int]) -> int:
def rec(a: int, k: int) -> int:
if a == 0:
return 0
elif a < 0 or k < 0:
return 50001
else:
return min(
rec(a - coins[k], k) + 1,
rec(a, k - 1))
return rec(amount, kind - 1)
これならきっとlru_cache
が効く
と思ったけど単純に@lru_cache()
つけただけだとTLE
キャッシュサイズのデフォルトが128なのでほとんど意味がなかった
@lru_cache(maxsize=None)
でAC
自前のキャッシュでもやってみる
def changes(amount: int, kind: int, coins: List[int]) -> int:
cache: List[List[int]] = [[False] * (kind + 1) for _ in range(amount + 1)]
def rec(a: int, k: int) -> int:
if a < 0 or k < 0:
return 50001
if cache[a][k]:
return cache[a][k]
if a == 0:
result = 0
else:
result = min(rec(a - coins[k], k) + 1, rec(a, k - 1))
cache[a][k] = result
return result
return rec(amount, kind - 1)
a < 0 or k < 0
のときはキャッシュ見なくても答えがわかるので
先に判定している