text: Coin Change | DP | Dynamic Programming C ++ 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 ) ; 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
code: #include <bits/stdc++.h> NEW_LINE int count ( int S [ ] , int m , int n ) { int table [ n + 1 ] ; memset ( table , 0 , sizeof ( table ) ) ; table [ 0 ] = 1 ; for ( int i = 0 ; i < m ; i ++ ) for ( int j = S [ i ] ; j <= n ; j ++ ) table [ j ] += table [ j - S [ i ] ] ; return table [ n ] ; }