Software Engineer

2 minute read

Problem Statement

leetcode problem link

My Solution [Accepted]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        N = len(coins)

        @cache
        def dp(i, curr_sum):
            if curr_sum == amount:
                return 0
            if curr_sum > amount or i == N:
                return float('inf')

            res = min(
                dp(i + 1, curr_sum),
                dp(i, curr_sum + coins[i]) + 1,
            )

            return res

        ans = dp(0, 0)
        if ans == float('inf'):
            return -1
        return ans

Convert to bottom-up approach (forward)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        N = len(coins)
        INF = float('inf')

        # dp[i][s] = answer to dp(i, s)
        dp = [[INF] * (amount + 1) for _ in range(N + 1)]

        # Base case: if current sum == amount → 0 coins needed
        for i in range(N + 1):
            dp[i][amount] = 0

        # Fill table
        # Because dp[i][s] depends on:
        #   dp[i + 1][s]     (row below)
        #   dp[i][s + coin]  (to the right)
        # We iterate i backwards and s backwards.
        for i in range(N - 1, -1, -1):
            for s in range(amount - 1, -1, -1):

                # Skip current coin
                skip = dp[i + 1][s]

                # Take current coin
                take = INF
                if s + coins[i] <= amount:
                    take = 1 + dp[i][s + coins[i]]

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

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

Convert to bottom-up approach (backward)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        N = len(coins)
        INF = float('inf')

        # dp[i][s] = min coins to make sum s using first i coins
        dp = [[INF] * (amount + 1) for _ in range(N + 1)]

        # Base case: 0 coins needed to make sum 0
        for i in range(N + 1):
            dp[i][0] = 0

        for i in range(1, N + 1):
            coin = coins[i - 1]
            for s in range(1, amount + 1):

                # Option 1: don't use this coin
                dp[i][s] = dp[i - 1][s]

                # Option 2: use this coin (unbounded, so stay in same row)
                if s >= coin:
                    dp[i][s] = min(dp[i][s],
                                   1 + dp[i][s - coin])

        return dp[N][amount] if dp[N][amount] != INF else -1

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

You may also enjoy