_322. Coin Change.md

322. Coin Change

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : September 24, 2024

Last updated : September 24, 2024

---

Related Topics : Array, Dynamic Programming, Breadth-First Search

Acceptance Rate : 45.01 %

---

Solutions

• m322.py

Python

m322.py

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @cache
        def recurs(amount: int) -> int :
            if amount == 0 :
                return 0
            minn = inf

            # goes in sorted order
            for c in coins :
                if amount - c < 0 :
                    break
                minn = min(minn, recurs(amount - c))
                if minn == 0 :
                    break

            return minn + 1

        coins.sort()

        # Is cached so it recalling it isn't a big deal
        return recurs(amount) if recurs(amount) != inf else -1