0322.md

322. Coin Change

Java Solution(s)

class Solution {
    int[] memo;
    public int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = i + 1;
        }
        return dp(coins, amount);
    }

    public int dp(int[] coins, int amount) {
        int res = amount + 1;
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        if (memo[amount] != amount + 1) {
            return memo[amount];
        }
        for (int coin: coins) {
            int tmp = dp(coins, amount - coin);
            if (tmp != -1) {
                res = Math.min(res, tmp + 1);
            }
        }
        memo[amount] = res == amount + 1 ? -1: res;
        return memo[amount];
    }
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin: coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
                }
            }
        }
        return dp[amount] == amount + 1 ? -1: dp[amount];
    }
}

Python Solutions

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        self.memo: list[int] = [-100] * (amount + 1)
        return self.dp(coins, amount)

    def dp(self, coins: list[int], amount: int) -> int:
        if (amount == 0):
            return 0
        if (amount < 0):
            return -1

        if (self.memo[amount] != -100):
            return self.memo[amount]

        res: int = amount + 1

        for coin in coins:
            subProblem: int = self.dp(coins, amount - coin)
            if subProblem != -1:
                res = min(subProblem + 1, res)

        self.memo[amount] = -1 if res == amount + 1 else res
        return self.memo[amount]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp: list[int] = [amount + 1] * (amount + 1)
        dp[0] = 0

        for i in range(amount + 1):
            for coin in coins:
                if i - coin < 0:
                    continue
                dp[i] = min(dp[i - coin] + 1, dp[i])
        return -1 if dp[i] == amount + 1 else dp[i]