DPL_1_A: Coin Changing Problem 続き

テキストのコードを見る
なんこれ超短い

def changes(amount: int, kind: int, coins: List[int]) -> int:

    T: List[int] = [50001] * (amount + 1)
    T[0] = 0

    for k in range(kind):
        for a in range(coins[k], amount + 1):
            T[a] = min(T[a], T[a - coins[k]] + 1)

    return T[amount]

これは自分で書いたコードを改良した延長線上にあるのか
それとも全然違う話なのか

ある種別のコインを1枚使った時とそのコインを使わないときに分ける、
ってところまでは同じだけどそこからは再帰とは逆方向に考えてる感じだなあ
11章のときもそんな感じだったか
こっちの考え方も身に着ける必要がありそう
とりあえず再帰で分割統治で考えてみる、っていうのはアリだとして
見えてきたところで逆転してみる、って感じかなあ

T[0]が0ってことは0円払う方法は0とおりってことなんだよな
そうでないとズレるっていうのはわかるけどちょっとピンと来てない

真ん中のヒントが二次元の表になってるから二次元配列を使うものだと思ってたけど
二次元は不要だったというのも衝撃
使うアルゴリズムのほうは一次元の動的計画法のアイコンになってた