518.Coin Change 2

num of solutions

The most interesting line is: $DP[j] += DP[j - coin];$ This line calculates the number of ways to get $j$ amount of money by using coins. The number is calculated by adding number of ways it can be done without using coin "coin" plus the number of ways it can be done with the coin "coin". The number of ways to get $j$ without using "coin" is $DP[j]$ which was already calculated while looping through other coins. The other way to get $j$ is to add "coin" to $j-coin$. So, it's just a matter of finding how many ways there are to get $j-coin$. It is actually $DP[j-coin]$ that was already calculated while looping through smaller $j$ values. So, as a result $DP[j] = DP[j]$ (number of ways to get j without using "coin") $+ DP[j-coin]$ (all other ways to get j).

def make_change(coins, n):
results = [0 for _ in range(n + 1)]
results[0] = 1
for coin in coins:
for i in range(coin, n + 1):
results[i] += results[i - coin]
return results[n]