Coin Change

🇷🇺 Название: Разменять монету
LeetCode: coin-change
Временная сложность: O(n*amount)
Пространственная сложность: O(amount)

Решение

from typing import List  


class Solution:  
    def coinChange(self, coins: List[int], amount: int) -> int:  
        variants = [float("inf")] * (amount + 1)  
        variants[0] = 0  

        for coin in coins:  
            for x in range(coin, amount + 1):  
                variants[x] = min(variants[x], variants[x - coin] + 1)  

        return variants[amount] if variants[amount] != float('inf') else -1

🇺🇸 Условие

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

🇷🇺 Условие

Примеры

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

Example 3:

Input: coins = [1], amount = 0
Output: 0

{
  "examples": [
    {
      "input": {
        "coins": [1,2,5],
        "amount": 11
      },
      "output": 3
    },
    {
      "input": {
        "coins": [2],
        "amount": 3
      },
      "output": -1
    },
    {
      "input": {
        "coins": [1],
        "amount": 0
      },
      "output": 0
    }
  ]
}

Ограничения

• \(1 \leq coins.length \leq 12\)
• \(1 \leq coins[i] \leq 2^{31} - 1\)
• \(0 \leq amount \leq 10^4\)

Потребление ресурсов

⏱ Time complexity: O(n*amount)

• Внешний цикл по coins длины n
• Внутренний цикл по значениям x = coin .. amount — максимум amount итераций
• На каждой итерации выполняется min(...) — O(1)

Итог: O(n*amount)

🧠 Space complexity: O(amount)

• Используется один список variants длины amount + 1
• Дополнительная память не используется

Итог: O(amount)

medium array dynamic-programming breadth-first-search

---

Metadata

• title_rus: Разменять монету
• difficulty: Medium
• leetcode_url: https://leetcode.com/problems/coin-change/
• topics: ['Array', 'Dynamic Programming', 'Breadth-First Search']
• time: O(n*amount)
• space: O(amount)
• grind75: True
• tags: ['Array', 'Breadth-First Search', 'Dynamic Programming', 'Medium', 'problem']
• git_revision_date_localized: 5 июля 2025 г.
• git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_revision_date_localized_tag:
• git_revision_date_localized_raw_date: 5 июля 2025 г.
• git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_revision_date_localized_raw_iso_date: 2025-07-05
• git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_revision_date_localized_raw_timeago:
• git_revision_date_localized_raw_custom: 05. июля 2025
• git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_site_revision_date_localized_tag:
• git_site_revision_date_localized: 5 июля 2025 г.
• git_site_revision_date_localized_raw_date: 5 июля 2025 г.
• git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_site_revision_date_localized_raw_iso_date: 2025-07-05
• git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_site_revision_date_localized_raw_timeago:
• git_site_revision_date_localized_raw_custom: 05. июля 2025