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