Dynamic Programming — Coin Change 2

Reference: https://www.themayor.eu/ro/france-could-soon-remove-1-and-2-eurocent-coins

LeetCode: https://leetcode.com/problems/coin-change-2/

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, assuming that you have infinite number of each kind of coin.

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

This is another classic dynamic programming problem where it can be solved with a more straightforward recursive approach and then optimized with iterative approach.

Solution 1:

State: 
  1. Parameters: total - current amount, start - index of the input   array (coins)
  2. Function: coinChange(total, start) - returns the total number of ways to change coins 
Transition: 
  1. Base case: total greater or equal to the amount
  2. Choices: all the combinations of coins to make up the amount
  3. Recurrence relation: coinChange(total, start) = coinChange(total, start) + coinChange(total + coins[i], i) for i in range(start, len(coins))
The reason of having the "start" parameter is because the order of coins doesn't matter. The "start" parameter prevents over-counting same combinations of coins.

Complexity Analysis:

Time Complexity: O(n^m)
n = len(coins)
m = amount / min(coins)
Think of recursion as a tree where each path represents a way to make up the amount and the height of the tree is the combination that has the most coins. Since the amount is fixed, the combination containing the most coins would be using the smallest coin. In the worst case, the tree's root node can have n child nodes. Therefore, the runtime becomes exponential.
Space Complexity: O(1)
With the recursion approach, no extra space is needed to calculate number of ways to make up the amount.

Solution 2:

The previous solution tries out all the possible combinations recursively and leads to an exponential runtime. If we drew out the recursion tree, we would notice that there are actually a lot of overlapping sub-problems. Instead of recursive approach, we can implement a bottom-up iterative approach and cache all the sub-problems' result in an array with size of the amount.
Each index in the array corresponds to some amount with its value being number of ways to make up this amount. In the end, we will just have to return dp[amount] (let the array be dp).

Complexity Analysis:

Time Complexity: O(n*m)
n = len(coins)
m = amount
Precisely speaking, the runtime would be a little less than O(n*m). If the coin is greater than 1 the inner loop will run (m - coin) iterations instead m, but here we're considering the worst case and ignoring the constant factors.
Space Complexity: O(m)
The extra space is used for caching. The array needs a size of amount to store all the sub-problems' result.

Performance:

Please leave a comment below if you have any suggestion/thought!

Happy coding :)