LeetCodeに挑戦：DP系問題 Medium (その3)

LeetCodeの方で動的計画法に関するスレッド、Dynamic Programming Questions Thread を見つけましたので、今回はその中にある Medium 問題を解いてみたいと思います。（DP系問題 Medium (その2)は こちら）

322. Coin Change

（問題）異なる額面のコイン(coins)とある金額(amount)が与えられます。 その amountとなる、最小のコインの数を答えて下さい。 その amount となるコインの組み合わせが存在しない場合は、-1を返して下さい。

（例1）Input:  coins = [ 1, 2, 5 ], amount = 11
Output: 3
　　　 説明：11 = 5 + 5 + 1

（例2）Input:  coins = [ 2 ], amount = 3
Output: -1

注意：同じ額のコインを何度使用してもかまいません。

解答例を以下に示します。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        #(1)
        dp = [0] + [float('INF') for a in range(amount)]
        #(2)
        for c in coins:
            #(3)
            for i in range(c,amount + 1):
                #(4)
                dp[i] = min(dp[i], dp[i-c] + 1)
        #(5)
        if dp[amount] != float('INF'):
            return dp[amount]
        else:
            return -1

　今回は、動的計画法(DP)の中でもボトムアップと呼ばれる方法で解いています（一方でトップダウンという方法がありますが、それは再帰を使うので正直苦手です。。）。戦略としては、与え得られた coins の中の要素単体で amount を達成できる枚数と、coins の中の複数の要素を組み合わせて達成できる枚数の、小さい方を配列 dp に書き込んでいきます。

それでは、上記のコードを個別に見ていきます。

        #(1)
        dp = [0] + [float('INF') for a in range(amount)]

　(1)では、 配列 dp を初期化しています。dp の要素番号は金額であり、0 から amount までの要素数（つまり amount + 1）をとります。たとえば dp[0] は 金額 0 を意味し、それを達成するコインの数は 0 であるはずなので、dp[0] = 0 となります。また、最終的に知りたいのは amount を達成するためのコインの数ですので、dp[amount]の値がこの問題の解答となります。 また、dp[0] 以外の初期値を 0にしてしまうと、最終的にその 0 が残った場合、0枚のコイン でその金額を達成できる意になってしまうので、あえて INF で初期化しています（INFの作成についてはこちら）。つまり INF が残った場合は、その金額は与えられた coins ではつくることができなかったという意になります。
　以上を今回は、少し格好をつけて、、一文で書いています。

        #(2)
        for c in coins:
            #(3)
            for i in range(c,amount + 1):
                #(4)
                dp[i] = min(dp[i], dp[i-c] + 1)

(2)の forループで、与えられるコインのすべてを個別みていきます。そして(3)の forループで、今みているコイン以上( c )から、amount までの範囲で dp を更新していきます。今みているコイン以上から、と設定するのを割と忘れがちで、例えば c = 2 となった場合は、額面2のコインのことをみている訳です。そして、dp[2] には、金額2を達成するためのコインの数を記入したい訳です。そうすると 今みている額面2のコインを1枚使えば良いですよね。よってdp[2] = 1 がいい感じになりそうです。では c = 2 の場合の dp[1]はどうなるかを考えると、基本無理ですよね。額面2のコインで、1となる金額をつくることはできません。よって (3)の forループ は、c からはじめています。
(4)で、dp を更新します。dp[ i ] か dp[ i – c ] + 1 の小さい方を採用しています。今一度、dp の要素番号が何を示していたかを確認すると、金額です。よってここでは i や c を用いて金額を示しています。そう考えれば dp[ i – c] の部分は今、更新したい 金額 i からコインの額面 c を引いた金額を示していることになります。そして + 1 とするのは、i – c の金額に c を足せば i に戻る（ i – c + c = i）となるので、枚数として 1 を足しています。

        #(5)
        if dp[amount] == float('INF'):
            return -1
        else:
            return dp[amount]

最後に、更新を終えた dp から dp[amount] の値を参照して、INF のままであれば（与えらえた amount をつくることはできなかったので） -1 を返し、そうでなければその値を返しています。

464. Can I Win

　（問題が何を言っているかわかならいので、一旦パスします）