No Of Ways To Make Change : Recursive and Dynamic Approch

noOfWaysCoins.py

#---------------------------------------------
#----------No Of Ways To Make Change----------
#---------------------------------------------

'''
Recursive solution

Logic:

    Suppose we are given with coins as [$1,$2,$3] and we have to make $5.
    We will use last coin and see where we will go with that decision and 
    also we will remove last coin and see where we reach with that decision

    Example we are given ([1,2,3],5)
    We divide this into two sub problems
    1. ([1,2,3],2) : Used last coin
    2. ([1,2],5) : Removed last coin

    We keep doing this until the amount we want to make become less that 0
    that means we can not make change by that way, or the we run out of coin's options
    then we return 0. In case amount we want to make gets down to 0 we return 1

    Recursion Tree for this problem


                                                                    ([1,2,3],5)
                                                                        |
                              |------------------------------------------------------------------------------------|              
                    ([1,2,3],2)                                                                                ([1,2],5)
                         |                                                                                         |           
            |-------------------------|                                       |-----------------------------------------------------------------------------|
        ([1,2,3],-1)              ([1,2],2)                               ([1,2],3)                                                                       ([1],5)
            |                         |                                       |                                                                              |
            |            |--------------------|                           |--------------------------------|                                        |-----------------|
        Return 0     ([1,2],0)             ([1],2)                   ([1,2],1)                          ([1],3)                                  ([1],4)            ([],5)
                         |                    |                         |                                   |                                        |                 |   
                         |           |----------------|           |-------------|                    |---------------|                      |-----------------|        |
                     Return 1    ([1],1)            ([],2)   ([1,2],-1)     ([1],1)                ([1],2)         ([],3)                 ([1],3)           ([],4)  Return 0
                                    |                |            |           |                       |              |                       |                 |
                              |-----------|          |            |     |-------------|         |-------------|      |                |-----------------|      |  
                          ([1],0)       ([],1)  Return 0     Return 0  ([1],0)   ([],1)     ([1],1)         ([],2)  Return 0        ([1],2)          ([],3)  Return 0
                            |           |                                  |        |            |             |                       |                |
                            |           |                                  |        |        |-----------|     |                |-----------------|     |
                         Return 1    Return 0                          Return 1  Return 0  ([1],0)     ([],1)  Return 0       ([1],1)          ([],2)  Return 0
                                                                                             |           |                      |                |
                                                                                        Return 1      Return 0          |-----------------|      |
                                                                                                                    ([1],0)             ([],1)  Return 0
                                                                                                                      |                    |
                                                                                                                      |                    |
                                                                                                                    Return 1            Return 0
    In total we got 5 Return 1 , so we can make $5 from [$1,$2,$3] in 5 ways

    With Recursion tree it is self explanatory how this is working
'''


def noOfWaysCoins(array, m , v):
    if v < 0 or m < 0:
        return 0
    if v == 0 :             
        return 1
    x = noOfWaysCoins(array,m,v-array[m])
    y = noOfWaysCoins(array,m-1,v)
    return x + y

print(noOfWaysCoins([1,2,3],2,5))


'''
Dynamic Programing approch

Logic :

    Suppose we are given [$1,$2,$3] and we have to make $5
    We will take a new array of size 1 plus the amount we want to make, like

     $0  $1  $2  $3  $4  $5  $6
    [ 0 , 0 , 0 , 0 , 0 , 0 , 0 ]

    In how many ways i can make $0. It is only 1 by not using coin. So, update the array

    [ 1 , 0 , 0 , 0 , 0 , 0 , 0 ]

    Now, we pick first coin i.e. $1. Now we can we make $0 with $1.
    We can not so we won't change our result at $0.
    Now can we make $1 with $1. So we found out one way.
    Now we will se whether we have seen any other method to make $1.
    At $1 location it says 0 ways previously found. So we update it by adding 1 to it

    [   1   1   0   0   0   0  ]

    Similarly for $2,$3,$4,$5

    [   1   1   1   0   0   0  ]

    [   1   1   1   1   0   0  ]

    [   1   1   1   1   1   0  ]

    [   1   1   1   1   1   1  ]

    Now we pick $2 coin we have. Since we can not make $0, $1 with it so we skip that
    with $2 we can make $2. yes, We were able to make $2 previously? (refer to previous resuls)
    Yes, we know 1 way to make $2 so we update the ways to 2

    [   1   1   2   1   1   1  ]

    Now can we make $3 with $2 ofcourse not, but can we make it with the help of other coin
    If we use are making $3 can we Take $2 from it we are left with $1.
    Can we make $1 with $1 we refer to table, yes we can make $1 with $1 in 1 way
    so we update $3 to 2
    (Remenber every time we are picking a coin we our using our previous coin results)

    [   1   1   2   2   1   1  ]

    Now can we make $4 with $2, well yes we can. 
    If i take $2 with $4 we are left with $2.
    Now we will refer to our previous result, with $2 in how may ways we can mae $2
    Results shows 2. SO we update $4 ways by 2. so it become 3

    [   1   1   2   2   3   1  ]

    Similar process will go on

    [   1   1   2   2   3   3  ]

    [   1   1   2   2   3   3  ]

    [   1   1   2   2   3   3  ]

    [   1   1   2   3   3   3  ]

    [   1   1   2   3   4   3  ]

    [   1   1   2   3   4   5  ]

    At last answer is the last element of our result array
'''

def noOfWaysCoins1(coins, v):
    result = [0 for x in range(v+1)]
    result[0] = 1
    for coin in coins:
        for i in range(coin,v+1):
            if coin <= i:
                result[i] += result[i-coin]
    return result[v]

print(noOfWaysCoins1([1,2,3],5))