Mediumdp
Решить задачу Coin Change (LeetCode 322)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 322. Минимальное число монет для суммы amount. DP bottom-up: dp[amt] = min(dp[amt - c] + 1). O(amount × len(coins)) время, O(amount) память.
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for amt in range(1, amount + 1):
for c in coins:
if c <= amt:
dp[amt] = min(dp[amt], dp[amt - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1Greedy не работает для произвольных denominations: coins=[1,3,4], amount=6 → greedy даёт 4+1+1=3, optimal 3+3=2. Top-down (memoization) — через @lru_cache. Связанные: Perfect Squares (279), Combination Sum IV (377).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.