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

Let dp_sum[i][j] be a number of ways to represent amount i such that we use only first j coins. We initialize the first column of this table with 1, because we can say there is one way to get amount = 0, using first j coins: do not take any coins. To find dp_sum[i][j] we need to look at the last coin taken, it consists of two terms:

  1. dp_sum[i][j-1], number of options, where we take only first j-1 coins
  2. dp_sum[i-coins[j]][j], number of options, where we removed coin number j and we need to find number of options for the rest amount.

Example: let us consider coins = [1,2,5] and amont = 5. Then table dp_sum will be equal to

  0 1 2 3 4 5
coin #0 (1) 1 1 1 1 1 1
coin #1 (2) 1 1 2 2 3 3
coin #2 (5) 1 1 2 2 3 4

Complexity time and space is O(amount *N), where N is number of different coins, because we need only O(1) to update each cell.

In code I use index i+1 instead of i, because we start from 1st column, not 0th.

Update Space complexity can be reduced to O(amount), because for every j we look at most one row back.

class Solution:
    def change(self, amount, coins):
        N = len(coins)
        if N == 0: return int(N == amount)
        
        dp_sum = [[0] * N for _ in range(amount + 1)]
        for i in range(N): dp_sum[0][i] = 1
        
        for i,j in product(range(amount), range(N)):
            dp_sum[i+1][j] = dp_sum[i+1][j-1]
            if i+1 - coins[j] >= 0:
                dp_sum[i+1][j] += dp_sum[i+1-coins[j]][j]           
                    
        return dp_sum[-1][-1]

Solution 2

This is classical problem for generation functions: you can see this example on wikipedia: number of ways to make change (https://en.wikipedia.org/wiki/Examples_of_generating_functions).

Howerer the main difficulty here is to make it work in time. What I did is I choose x = 2^32, spend like 4 hours, trying different ways to multiply polynomials, using convolutions and optimizing code to avoid TLE and here is the result.

Update:

Let us go through example target = 5 and coins = [1, 2, 5]

  1. We build 3 generating polynoms: 1+x+x^2+x^3+x^4+x^5, 1+x^2+x^4 and 1+x^5. What we need to do now is to multiply these polynomials and evaluate coefficient before term with degree target. Indeed: (1+x+x^2+x^3+x^4+x^5)*(1+x^2+x^4)*(1+x^5) = ... + x*x^4*1 + 1*1*x^5 + x^3*x^2*1 + x^5*1*1, there is 4 possible ways to get degree 5.
  2. Note, that if all coefficients are less than some big number N, say N=1000 for example and polynom = 13x^2 + 6x + 3, than polynom(1000) = 13006003, so we can easily distinguish coefficients for each degree, if we look at our number as number in base 1000.
  3. To make it faster we use the fact (1+x+x^2+x^3+x^4+x^5) = (x^6-1)/(x-1), (1+x^2+x^4) = (x^6-1)/(x^2-1) and 1+x^5=(x^10-1)/(x^5-1).
  4. We take N=2^32, because it is given in statement that we can never get numbers more than N.
  5. Substitute N=2^32 into our polynom and evaluate it! Python allows as to do computations of big numbers.
  6. Optimisations: use a lot of bit manipulations to avoid TLE.
class Solution:
    def change(self, amount, coins):
        S = [(((1<<(32*(amount//i*i + i)))) - 1)//((1<<(i*32)) - 1) for i in coins]
        prodd = 1
        
        for i in S: prodd = (prodd * i) & ((1<<((amount +1)*32))-1)
        return prodd>>(32*amount)

We can write it as Oneliners in the following ways - thanks https://leetcode.com/joric/ for this!

return reduce(lambda p,i:(p*i)&(1<<((amount+1)*32))-1,[((1<<(32*(amount//i*i+i)))-1)//((1<<(i*32))-1) for i in coins],1)>>(32*amount)

return list(accumulate(coins,lambda p,i:(p*(((1<<(32*(amount//i*i+i)))-1)//((1<<(i*32))-1)))&((1<<((amount+1)*32))-1),initial=1))[-1]>>(32*amount)

If you have any questions, feel free to ask. If you like solution and explanations, please Upvote!

If you like the solution, you can upvote it on leetcode discussion section: Problem 0518