Coin Change - Count Number of Ways (DP variant)

Problem: Coin Change - Number of Ways (DP variant) Given an integer array coins representing different coin denominations and an integer amount representing a target total. Compute the number of distinct combinations to make up amount using the coins. You may use each coin denomination unlimited times. Combinations are order-independent (e.g., 1+2 and 2+1 are the same combination). Return the number of combinations. I/O Format Input: Line 1: amount Line 2: space-separated coins Output: the number of combinations (integer) Constraints 0 <= amount <= 5000 1 <= len(coins) <= 300 1 <= coins[i] <= 5000 The result fits in signed 64-bit integer Example Input: 5 1 2 5 Output: 4 Example Input 5 1 2 5 Output 4