ゼロから始めるLeetCode Day102「322. Coin Change」

• 概要
• 問題
• 解法

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day101「387. First Unique Character in a String

次回
ゼロから始めるLeetCode Day102「322. Coin Change」

Twitterやってます。

問題

322. Coin Change
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、異なる額面のコインと合計金額が与えられます。その金額を作るのに必要なコインの数が最も少ないコインを計算する関数を実装してください、という問題です。なお、コインのどの組み合わせでもその金額を作ることができない場合は、-1を返す。

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

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

解法

典型的なナップザック問題ですね。

ちなみにナップザック問題というのはこのようなもので、与えられた条件の中から最適な場合を求めるための例として挙げられる問題群のことです。

そして、それらを解くために動的計画法を使うのが一般的と言われています。

ということで動的計画法を使って解いてみました。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0] + [amount + 1] * amount
        dp[0] = 0
        for i in range(amount+1):
            for c in coins:
                if i >= c:
                    dp[i] = min(dp[i],dp[i-c]+1)
        return -1 if dp[amount] > amount else dp[amount]
# Runtime: 1604 ms, faster than 51.63% of Python3 online submissions for Coin Change.
# Memory Usage: 14 MB, less than 65.21% of Python3 online submissions for Coin Change.

こんな感じになりました。ただ、最大数を取る問題と違って最小値を取る問題のため、min関数を使っている点に注意してください。
それ以外は至って普通の動的計画法です。
最後のは内包表記といって分岐などを一行にまとめて返せるのでコードがすっきりします。意外と重宝します。

では今回はここまで。お疲れ様でした。