322. Coin Change

LeetCode medium original: C# #array #backtracking #csharp #leetcode #math #medium #recursion

题目文本会按所选界面语言从俄语翻译；代码保持不变。

LeetCode Static

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

return минимальное количество монет, необходимых для составления этой суммы. Если эту сумму невозможно составить с помощью комбинации монет, return -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++ 解法

自动草稿，提交前请检查

#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, найдена, return минимальное количество монет, иначе return -1.

😎

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。