Coin Change

  # ----------------------------------------
  # 3. Coin Change - Unbounded Knapsack DP
  #
  # Problem: Given coins of different denominations and amount,
  # find minimum number of coins needed to make the amount.
  #
  # Input: coins = [1, 3, 4], amount = 6
  # Output: 2 (3 + 3 = 6)
  #
  # Time Complexity: O(amount * coins.length)
  # Space Complexity: O(amount)
  # ----------------------------------------
  def coin_change(coins, amount)
    dp = Array.new(amount + 1, Float::INFINITY)
    dp[0] = 0
    
    (1..amount).each do |i|
      coins.each do |coin|
        if coin <= i && dp[i - coin] != Float::INFINITY
          dp[i] = [dp[i], dp[i - coin] + 1].min
          puts "Amount #{i}: using coin #{coin}, min coins = #{dp[i]}"
        end
      end
    end
    
    result = dp[amount] == Float::INFINITY ? -1 : dp[amount]
    puts "Minimum coins for amount #{amount}: #{result}"
    result