Hackerrank: Coin Change

Solve The Coin Change Problem

Given m coins we need to make change of amount n. To solve this we reduce the problem into sub-problems

1. Get change of amount n with without using mth coin
2. Get the change of amount n with using the mth coin

We can make a matrix to visualize this problem where coins are on x axis and amounts are on y axis

A column below represents change using the group of coins in the header. With coin of value 1 we have only 1 way to make change for any amount

With an additional coin we have 2 options, whether we use the coin or not. If we do not wish to use the new coin we will simply take the value in the left cell which represents change for amount n with rest of coins.

To make sure that we are using the mth coin, we can take all the ways to make change for amount n-m and add mth coin to make change for n. We can get this value from the same column, at location m steps above current cell.

Suppose we have 3 coins and we want to make change for 6. Then we first find ways to make change by using 1, then 1 and 2 and finally using 1, 2 and 3.

For the first column all values are 1, for the second column left cells are 1 and we need to go up 2 steps. In the third column from fourth cell onwards we can go up 3 steps to get change for n-3 and use left cell to get change for n without using 3. Try to construct the table yourself to get a hang of the algorithm.

Remarks:

1. O(m*n) time complexity to calculate change for all amounts from 1 to m for each coin. This is same as the size of grid used above.
2. O(m) space complexity, we only need space to store change for all amounts less than or equal to m. This is same as size of the column used above.

from collections import defaultdict
n, m = map(int, raw_input().strip().split(" "))
nums = map(int, raw_input().strip().split(" "))
dp = defaultdict(int)
dp[0] = 1
for i in range(0, m):
    for j in range(nums[i], n + 1):
        dp[j] += dp[j - nums[i]]
print dp[n]