Coin Change | DP | Dynamic Programming Python implementation of Coin Change problem ; table [ i ] will be storing the number of solutions for value i . We need n + 1 rows as the table is constructed in bottom up manner using the base case ( n = 0 ) Initialize all table values as 0 ; Base case ( If given value is 0 ) ; Pick all coins one by one and update the table [ ] values after the index greater than or equal to the value of the picked coin ; Driver program to test above function
def count ( S , m , n ) : NEW_LINE INDENT table = [ 0 for k in range ( n + 1 ) ] NEW_LINE table [ 0 ] = 1 NEW_LINE for i in range ( 0 , m ) : NEW_LINE INDENT for j in range ( S [ i ] , n + 1 ) : NEW_LINE INDENT table [ j ] += table [ j - S [ i ] ] NEW_LINE DEDENT DEDENT return table [ n ] NEW_LINE DEDENT arr = [ 1 , 2 , 3 ] NEW_LINE m = len ( arr ) NEW_LINE n = 4 NEW_LINE x = count ( arr , m , n ) NEW_LINE print ( x ) NEW_LINE