Coin Change Ii - Leetcode Solution

Problem Statement: You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have an infinite number of each kind of coin.

Example 1: Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1

Example 2: Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up by any combination of the coins.

Solution: This problem can be solved using dynamic programming. Let dp[i][j] be the number of combinations that make up the amount j using the first i coins. We can calculate the value of dp[i][j] using the following recursive formula:

dp[i][j] = dp[i-1][j] // exclude the ith coin + dp[i][j-coins[i-1]] // include ith coin

The first term of the formula is the number of combinations we can make without using the ith coin. The second term is the number of combinations we can make by including the ith coin. We use i-1 instead of i for indexing the coin array since we start the indexing from 0.

To initialize the dp array, we can set dp[0][0] to 1 since there is one way to make up the amount 0 using 0 coins. We can also set dp[0][j] to 0 for all j > 0 since there are no coins to use.

Finally, the solution to the problem is given by dp[n][amount], where n is the length of the coins array.

Time Complexity: The time complexity of the solution is O(nm) where n is the number of coins and m is the amount, since we need to fill a table of size n*m.

Space Complexity: The space complexity of the solution is also O(nm), since we need to store the dp array.

Python code:

def change(amount: int, coins: List[int]) -> int: n = len(coins) dp = [[0 for _ in range(amount+1)] for _ in range(n+1)] dp[0][0] = 1 for i in range(1, n+1): dp[i][0] = 1 for j in range(1, amount+1): dp[i][j] = dp[i-1][j] if j >= coins[i-1]: dp[i][j] += dp[i][j-coins[i-1]] return dp[n][amount]

Java code:

class Solution { public int change(int amount, int[] coins) { int n = coins.length; int[][] dp = new int[n+1][amount+1]; dp[0][0] = 1; for (int i = 1; i <= n; i++) { dp[i][0] = 1; for (int j = 1; j <= amount; j++) { dp[i][j] = dp[i-1][j]; if (j >= coins[i-1]) { dp[i][j] += dp[i][j-coins[i-1]]; } } } return dp[n][amount]; } }

Both codes have the same time and space complexity.

1