LeetCode-Coin Change Problem (Python)

Tags: , ,

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

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

Solution:

To solve a minimization problem, we need to identify the subproblem, and use the subproblem to solve the original problem. Here I will talk about how to come up a solution based on dynamic programming with O(mn) space complexity. Then we optimize the space complexity to O(n).

Lets number the coins from 1 to M.  Suppose we know the answer wheun only use the coins from 1 to M - 1, how can we use that to solve the problem using coins from 1 to M?

Let’s define Num(m, n) as the minimum number of coins  to get amount n when the coins from 1 to m are used.

Now we want to solve Num(m+1, n), which means the minimum number of coins to get amount n when coins from 1 to m+1 are used.

Actually, there are only two options: use the (m + 1) th coin, or not use it.

There are two cases:

if coin[m + 1] is larger than n, we can not use it. so Num(m + 1, n) = Num(m, n)

else Num(m + 1, n) = Min( Num(m, n), Num(m + 1, n - coin[m + 1]) + 1), where coin[m + 1] denotes the value of coin m + 1

Be careful, as there are infinite coins, Num(m + 1, n - coin[m + 1]) should be used here. If you use Num(m, n - coin[m + 1]), it means each coins can only be used once.

Here is the implementation:

As the space complexity is O(M * N) is cann’t pass big N. We can reduce the space complexity to O(N) as for each run there is only two rows affected.

Define Num[n] as the minimum number of coins should be used, then we iterate through the m coins, and check whether Num[n] is larger than Num[n - coins[m]] + 1 when n is larger than coins[m].

Here is the optimized implementation with O(n) space complexity.