leetcode-322 Coin Change

# You are given an integer array coins representing coins of different
# denominations and an integer amount representing a total amount of money.
# Return the fewest number of coins needed to make up that amount.
# If that amount cannot be made up by any combination, return -1.
# You may assume you have an infinite number of each kind of coin.
#
# Example 1:
# Input: coins = [1,2,5], amount = 11
# Output: 3
# Explanation: 11 = 5 + 5 + 1
#
# Example 2:
# Input: coins = [2], amount = 3
# Output: -1
#
# Example 3:
# Input: coins = [1], amount = 0
# Output: 0
#
# Constraints:
# 1 <= coins.length <= 12
# 1 <= coins[i] <= 2^31 - 1
# 0 <= amount <= 10^4

class Solution:
    # Bottom-up DP
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp[i] = minimum coins to make amount i
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0  # Base case: 0 coins needed for amount 0

        # For each amount from 1 to target
        for i in range(1, amount + 1):
            # Try each coin
            for coin in coins:
                if coin <= i:
                    # If we use this coin, we need dp[i - coin] + 1 coins
                    dp[i] = min(dp[i], dp[i - coin] + 1)

        return dp[amount] if dp[amount] != float('inf') else -1

    # Top-down DP with Memoization
    def coinChange2(self, coins: List[int], amount: int) -> int:
        memo = {}

        def dp(remaining):
            # Base cases
            if remaining == 0:
                return 0
            if remaining < 0:
                return float('inf')
            if remaining in memo:
                return memo[remaining]

            # Try each coin
            min_coins = float('inf')
            for coin in coins:
                result = dp(remaining - coin)
                if result != float('inf'):
                    min_coins = min(min_coins, result + 1)

            memo[remaining] = min_coins
            return min_coins

        result = dp(amount)
        return result if result != float('inf') else -1

# Time Complexity: O(amount * len(coins))
# Space Complexity: O(amount) for dp array
#
# DP Recurrence: dp[i] = min(dp[i - coin] + 1) for all coins <= i
# Pattern: Unbounded Knapsack (can use each item unlimited times)