Coin Change Combinations

Dynamic Programming Coin Change Dp Easy Medium

Problem Description

Given an integer amount and an array of distinct positive integers coins representing the denominations of coins, find the number of ways to make up the amount using any combination of the coins. You may assume that you have an infinite supply of each coin.

Example:

Input: amount = 5, coins = [1, 2, 5]

Output: 4

Explanation: There are four ways to make up the amount 5:

  1. 5 = 5
  2. 5 = 2 + 2 + 1
  3. 5 = 2 + 1 + 1 + 1
  4. 5 = 1 + 1 + 1 + 1 + 1

Use dynamic programming to solve this problem efficiently. This exercise not only hones your DP skills but also serves as a great puzzle challenge on this day of the month.


Function Signature

Your task is to implement the following function:

function coinChange(amount, coins) {
    // Your code here
    // Return an integer representing the number of ways to form the given amount
}

Note: Assume that the order of coins does not matter (i.e., [1,2,2] is the same as [2,1,2]).