Standard Bar Dynamic Programming · DP on Subsequences O(n*amount) · O(amount)
A vending operator settles the day's coin boxes and wants to know in how many distinct ways each till total can be composed from the denominations on hand. Hoppers hold unlimited stock of every denomination, and order does not matter — a pile with two 2s and one 1 is the same composition regardless of counting sequence. The ledger reports one number per till: the count of compositions.
Input: An integer amount and an array coins of distinct denominations.
Output: Return the number of combinations of coins that sum to amount, where each denomination may repeat and order is irrelevant.
1 <= len(coins) <= 3001 <= coins[i] <= 50000 <= amount <= 5000the answer fits in a 32-bit signed integerInput: {"amount":5,"coins":[1,2,5]}
Output: 4
5; 2+2+1; 2+1+1+1; 1+1+1+1+1 — four unordered compositions.
Input: {"amount":3,"coins":[2]}
Output: 0
Odd totals are impossible with only 2s.