103. Coin Change: Count the Ways
MediumDynamic programming
Given coin denominations coins (unlimited supply of each) and an amount, return how many different combinations of coins add up to the amount. Combinations that use the same coins in a different order count once.
Example 1
Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1
Constraints
0 ≤ amount ≤ 50001 ≤ coins.length ≤ 300Denominations are distinctThe answer fits in a 32-bit signed integer