Count ways to make change (DP)

Problem

You are given an integer amount and an array of positive, distinct integers coins, where each coin value can be used unlimited times.

Return the number of distinct combinations of coins that sum to exactly amount.

Notes:

• The order does not matter . For example, 2+1 and 1+2 are the same combination.
• If amount = 0 , there is exactly one way: choose no coins.

Input/Output

• Input: integer amount , integer array coins
• Output: integer ways

Examples

• amount = 5, coins = [1,2,5] → 4
  • Combinations: 5 , 2+2+1 , 2+1+1+1 , 1+1+1+1+1
• amount = 3, coins = [2] → 0
• amount = 0, coins = [1,2] → 1

Constraints (assume)

• 0 ≤ amount ≤ 10^4
• 1 ≤ len(coins) ≤ 300
• Result fits in 64-bit signed integer