Coin Change
Medium · Dynamic Programming · about 25 minutes
Asked at Amazon, Coinbase, Google, PayPal, Stripe, Intuit, Visa, Capital One, Plaid, Ramp, Chime, SoFi, Affirm, Klarna, Revolut, American Express, Rippling, Gusto, Brex, Mercury, Kraken.
Given coin denominations and a target amount, return the fewest coins needed to make that amount, or -1 if impossible. You have unlimited coins of each kind.