518. Coin Change II

LeetCode medium original: C# #array #bit-manipulation #csharp #dynamic-programming #leetcode #medium #recursion #string

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

Вам дан số nguyên mảng coins, представляющий монеты разных номиналов, и số nguyên amount, представляющее общую сумму денег.

return количество комбинаций, которые составляют эту сумму. Если эту сумму нельзя составить никакой комбинацией монет, return 0.

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

Ответ гарантированно вписывается в знаковое 32-битное số nguyên.

Ví dụ:

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

Output: 4

Explanation: there are four ways to make up the amount:

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

C# lời giải

đã khớp/gốc

public class Solution {
    public int Change(int amount, int[] coins) {
        int[,] memo = new int[coins.Length, amount + 1];
        for (int i = 0; i < coins.Length; i++) {
            for (int j = 0; j <= amount; j++) {
                memo[i, j] = -1;
            }
        }
        return NumberOfWays(0, amount, coins, memo);
    }
    private int NumberOfWays(int i, int amount, int[] coins, int[,] memo) {
        if (amount == 0) return 1;
        if (i == coins.Length) return 0;
        if (memo[i, amount] != -1) return memo[i, amount];
        if (coins[i] > amount) {
            memo[i, amount] = NumberOfWays(i + 1, amount, coins, memo);
        } else {
            memo[i, amount] = NumberOfWays(i, amount - coins[i], coins, memo) 
                            + NumberOfWays(i + 1, amount, coins, memo);
        }
        return memo[i, amount];
    }
}

C++ lời giải

bản nháp tự động, xem lại trước khi gửi

#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 Change(int amount, vector<int>& coins) {
        int[,] memo = new int[coins.size(), amount + 1];
        for (int i = 0; i < coins.size(); i++) {
            for (int j = 0; j <= amount; j++) {
                memo[i, j] = -1;
            }
        }
        return NumberOfWays(0, amount, coins, memo);
    }
    private int NumberOfWays(int i, int amount, vector<int>& coins, int[,] memo) {
        if (amount == 0) return 1;
        if (i == coins.size()) return 0;
        if (memo[i, amount] != -1) return memo[i, amount];
        if (coins[i] > amount) {
            memo[i, amount] = NumberOfWays(i + 1, amount, coins, memo);
        } else {
            memo[i, amount] = NumberOfWays(i, amount - coins[i], coins, memo) 
                            + NumberOfWays(i + 1, amount, coins, memo);
        }
        return memo[i, amount];
    }
}

Java lời giải

đã khớp/gốc

class Solution {
    public int change(int amount, int[] coins) {
        int[][] memo = new int[coins.length][amount + 1];
        for (int i = 0; i < coins.length; i++) {
            Arrays.fill(memo[i], -1);
        }

        return numberOfWays(0, amount, coins, memo);
    }

    private int numberOfWays(int i, int amount, int[] coins, int[][] memo) {
        if (amount == 0) {
            return 1;
        }
        if (i == coins.length) {
            return 0;
        }
        if (memo[i][amount] != -1) {
            return memo[i][amount];
        }

        if (coins[i] > amount) {
            memo[i][amount] = numberOfWays(i + 1, amount, coins, memo);
        } else {
            memo[i][amount] = numberOfWays(i, amount - coins[i], coins, memo) + numberOfWays(i + 1, amount, coins, memo);
        }
        return memo[i][amount];
    }
}

JavaScript lời giải

đã khớp/gốc

var change = function(amount, coins) {
    const memo = Array.from({ length: coins.length }, () => Array(amount + 1).fill(-1));

    const numberOfWays = (i, amount) => {
        if (amount === 0) return 1;
        if (i === coins.length) return 0;
        if (memo[i][amount] !== -1) return memo[i][amount];

        if (coins[i] > amount) {
            memo[i][amount] = numberOfWays(i + 1, amount);
        } else {
            memo[i][amount] = numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount);
        }
        return memo[i][amount];
    };

    return numberOfWays(0, amount);
};

Python lời giải

đã khớp/gốc

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        def numberOfWays(i: int, amount: int) -> int:
            if amount == 0:
                return 1
            if i == len(coins):
                return 0
            if memo[i][amount] != -1:
                return memo[i][amount]

            if coins[i] > amount:
                memo[i][amount] = numberOfWays(i + 1, amount)
            else:
                memo[i][amount] = numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount)
            
            return memo[i][amount]

        memo = [[-1] * (amount + 1) for _ in range(len(coins))]
        return numberOfWays(0, amount)

Go lời giải

đã khớp/gốc

func change(amount int, coins []int) int {
    memo := make([][]int, len(coins))
    for i := range coins {
        memo[i] = make([]int, amount + 1)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

    var numberOfWays func(i, amount int) int
    numberOfWays = func(i, amount int) int {
        if amount == 0 {
            return 1
        }
        if i == len(coins) {
            return 0
        }
        if memo[i][amount] != -1 {
            return memo[i][amount]
        }

        if coins[i] > amount {
            memo[i][amount] = numberOfWays(i + 1, amount)
        } else {
            memo[i][amount] = numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount)
        }
        return memo[i][amount]
    }

    return numberOfWays(0, amount)
}

Algorithm

Создайте двумерный mảng memo с n chuỗiми и amount + 1 столбцами. Инициализируйте значения -1, чтобы указать, что подBài toán еще не решена. Реализуйте рекурсивный метод numberOfWays, который принимает два параметра: индекс i текущей рассматриваемой монеты и оставшуюся сумму, которую нужно составить. Он returns количество способов составить сумму, используя монеты, начиная с индекса i до последней монеты.

Если amount == 0, return 1. Мы можем выбрать один способ, не выбирая ни одной монеты, чтобы составить сумму 0. Если i == n, у нас не осталось монет для составления суммы, return 0. Если эта подBài toán уже решена, т.е. memo[i][amount] != -1, return memo[i][amount]. Если значение текущей монеты превышает сумму, мы не можем её использовать. Рекурсивно вызовите numberOfWays(i + 1, amount), присвойте результат memo[i][amount] и return его.

В противном случае, добавьте общее количество способов составить сумму, как выбирая текущую монету, так и игнорируя её. Сложите значения numberOfWays(i, amount - coins[i]) и numberOfWays(i + 1, amount), сохраните результат в memo[i][amount] и return его. return numberOfWays(0, amount), ответ на исходную задачу.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.