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 ; Driver Code
code: using System ; class GFG { static int count ( int [ ] S , int m , int n ) { int [ ] table = new int [ n + 1 ] ; 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 ] ; } public static void Main ( ) { int [ ] arr = { 1 , 2 , 3 } ; int m = arr . Length ; int n = 4 ; Console . Write ( count ( arr , m , n ) ) ; } }