322. Coin Change

[sophryu99]

Approach

https://leetcode.com/problems/coin-change/description/

1. Initialize a dp array with size of amount. dp[i]: fewest number of coins that sums to i
2. For every i (the amount to be summed up to), iterate through the coin array and check
3. f the coin is less than or equal to i, get the dp[i - coin] value, and compare it with the current dp[i] val. Reset dp[i] with smaller value -> dp[i] = min(dp[i], dp[i - coin] + 1)
4. If the last element of the dp array has not been reached, return -1

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # BFS approach
        # dp array with the size of amount
        # dp[i] is the fewest number of coins need to sum up to i
        dp = [0] + [float('inf')] * amount
        for i in range(1, amount + 1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i - coin] + 1)

        if dp[-1] == float('inf'):
            return -1
        return dp[-1]

N: amount, M: number of coins

• Time Complexity: O(N * M) as for every amount, every coins are tried out
• Space Complexity: O(N) dp array of size N