BinarySearch 0216 Making Change Sequel

Problem statement

https://binarysearch.com/problems/Making-Change-Sequel/

Solution

Equal to Leetcode 0322. Coin Change, but now we need to use table to avoid TLE

Complexity

It is O(amount * n) for time and O(amount) for space.

Code

class Solution:
    def solve(self, denominations, amount):
        dp = [0] + [float("inf")] * amount

        for y in range(0, amount + 1):
            for coin in denominations:
                if y - coin < 0:
                    continue
                dp[y] = min(dp[y], dp[y - coin] + 1)
        return -1 if dp[-1] == float("inf") else dp[-1]