kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

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のときはキャッシュ見なくても答えがわかるので
先に判定している