Problem of The Day: Coin Change

6 min read 1335 words

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        res = float('inf')
        memo = {}
        def dp(i, remain):
            if remain == 0:
                return 0
            if i == len(coins) or remain < 0:
                return float('inf')
            if (i, remain) in memo:
                return memo[(i, remain)]

            take = dp(i, remain - coins[i]) + 1
            skip = dp(i + 1, remain)
            memo[(i, remain)] = min(take ,skip)
            return memo[(i, remain)]

        for i in range(len(coins)):
            res = min(res, dp(i, amount))

        return res if res != float('inf') else -1

time: O(n * m) where n is number of coins and m is the amount space: O(n * m)

Dynamic Programming - Bottom up

from typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        INF = amount + 1  # larger than any possible minimal coin count

        # dp[i][j] = min coins needed to make j using coins[i:]
        dp = [[INF] * (amount + 1) for _ in range(n + 1)]

        # Base case: 0 amount requires 0 coins for any i
        for i in range(n + 1):
            dp[i][0] = 0

        # Fill from bottom (i = n-1 down to 0), amounts from 1..amount
        for i in range(n - 1, -1, -1):
            for j in range(1, amount + 1):
                # skip current coin => move to i+1
                skip = dp[i + 1][j]

                # take current coin (if it fits) => stay on i, reduce amount
                take = INF
                if j >= coins[i]:
                    take = dp[i][j - coins[i]] + 1

                dp[i][j] = min(take, skip)

        ans = dp[0][amount]
        return ans if ans < INF else -1

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        int n = coins.Length;
        // Use a large value that won't overflow when +1 is added
        int INF = 1_000_000_000;

        // dp[i][j] = min coins using coins from index i to n-1 to get amount j
        int[][] dp = new int[n + 1][];
        for (int i = 0; i <= n; i++) {
            dp[i] = new int[amount + 1];
            Array.Fill(dp[i], INF);
            // Base case: If remain is 0, we need 0 coins
            dp[i][0] = 0;
        }

        // Iterate backwards through coins (matching your recursive i + 1 logic)
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j <= amount; j++) {
                // Option 1: Skip the current coin
                int skip = dp[i + 1][j];

                // Option 2: Take the current coin (only if it fits)
                int take = INF;
                if (j >= coins[i]) {
                    take = dp[i][j - coins[i]] + 1;
                }

                dp[i][j] = Math.Min(take, skip);
            }
        }

        int result = dp[0][amount];
        return result >= INF ? -1 : result;
    }
}

Editorial

Approach 2 (Dynamic programming - Top down) [Accepted]

from functools import lru_cache


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

        @lru_cache(None)
        def dfs(rem):
            if rem < 0:
                return -1
            if rem == 0:
                return 0
            min_cost = float('inf')
            for coin in coins:
                res = dfs(rem - coin)
                if res != -1:
                    min_cost = min(min_cost, res + 1)
            return min_cost if min_cost != float('inf') else -1

        return dfs(amount)

Approach 3 (Dynamic programming - Bottom up) [Accepted]

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

        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1