322. Coin Change

LeetCode medium оригинал: C# #array #backtracking #csharp #leetcode #math #medium #recursion

LeetCode Static

Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.

Верните минимальное количество монет, необходимых для составления этой суммы. Если эту сумму невозможно составить с помощью комбинации монет, верните -1.

Вы можете предположить, что у вас есть неограниченное количество монет каждого типа.

Пример

Input: coins = [1,2,5], amount = 11

Output: 3

Explanation: 11 = 5 + 5 + 1

C# решение

сопоставлено/оригинал

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        return CoinChange(0, coins, amount);
    }
    private int CoinChange(int idxCoin, int[] coins, int amount) {
        if (amount == 0) return 0;
        if (idxCoin < coins.Length && amount > 0) {
            int maxVal = amount / coins[idxCoin];
            int minCost = int.MaxValue;
            for (int x = 0; x <= maxVal; x++) {
                if (amount >= x * coins[idxCoin]) {
                    int res = CoinChange(idxCoin + 1, coins, amount - x * coins[idxCoin]);
                    if (res != -1)
                        minCost = Math.Min(minCost, res + x);
                }
            }
            return minCost == int.MaxValue ? -1 : minCost;
        }
        return -1;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int CoinChange(vector<int>& coins, int amount) {
        return CoinChange(0, coins, amount);
    }
    private int CoinChange(int idxCoin, vector<int>& coins, int amount) {
        if (amount == 0) return 0;
        if (idxCoin < coins.size() && amount > 0) {
            int maxVal = amount / coins[idxCoin];
            int minCost = int.MaxValue;
            for (int x = 0; x <= maxVal; x++) {
                if (amount >= x * coins[idxCoin]) {
                    int res = CoinChange(idxCoin + 1, coins, amount - x * coins[idxCoin]);
                    if (res != -1)
                        minCost = min(minCost, res + x);
                }
            }
            return minCost == int.MaxValue ? -1 : minCost;
        }
        return -1;
    }
}

Java решение

сопоставлено/оригинал

public class Solution {

    public int coinChange(int[] coins, int amount) {
        return coinChange(0, coins, amount);
    }

    private int coinChange(int idxCoin, int[] coins, int amount) {
        if (amount == 0) return 0;
        if (idxCoin < coins.length && amount > 0) {
            int maxVal = amount / coins[idxCoin];
            int minCost = Integer.MAX_VALUE;
            for (int x = 0; x <= maxVal; x++) {
                if (amount >= x * coins[idxCoin]) {
                    int res = coinChange(idxCoin + 1, coins, amount - x * coins[idxCoin]);
                    if (res != -1)
                        minCost = Math.min(minCost, res + x);
                }
            }
            return (minCost == Integer.MAX_VALUE) ? -1 : minCost;
        }
        return -1;
    }
}

JavaScript решение

сопоставлено/оригинал

var coinChange = function(coins, amount) {
    return coinChangeHelper(0, coins, amount);
};

var coinChangeHelper = function(idxCoin, coins, amount) {
    if (amount === 0) return 0;
    if (idxCoin < coins.length && amount > 0) {
        let maxVal = Math.floor(amount / coins[idxCoin]);
        let minCost = Number.MAX_SAFE_INTEGER;
        for (let x = 0; x <= maxVal; x++) {
            if (amount >= x * coins[idxCoin]) {
                let res = coinChangeHelper(idxCoin + 1, coins, amount - x * coins[idxCoin]);
                if (res !== -1) {
                    minCost = Math.min(minCost, res + x);
                }
            }
        }
        return minCost === Number.MAX_SAFE_INTEGER ? -1 : minCost;
    }
    return -1;
};

Python решение

сопоставлено/оригинал

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        return self._coinChange(0, coins, amount)

    def _coinChange(self, idxCoin: int, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        if idxCoin < len(coins) and amount > 0:
            maxVal = amount // coins[idxCoin]
            minCost = float('inf')
            for x in range(maxVal + 1):
                if amount >= x * coins[idxCoin]:
                    res = self._coinChange(idxCoin + 1, coins, amount - x * coins[idxCoin])
                    if res != -1:
                        minCost = min(minCost, res + x)
            return -1 if minCost == float('inf') else minCost
        return -1

Go решение

сопоставлено/оригинал

package main

import (
    "fmt"
    "math"
)

func coinChange(coins []int, amount int) int {
    return coinChangeHelper(0, coins, amount)
}

func coinChangeHelper(idxCoin int, coins []int, amount int

Algorithm

Инициализация и вызов функции backtracking

Инициализируйте переменные для хранения минимального количества монет и вызовите функцию backtracking с начальными параметрами.

Функция backtracking

Внутри функции backtracking для каждой монеты из массива coins:

Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет.

Возврат результата

Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.