text: Number of paths with exactly k coins | A Dynamic Programming based C # program to count paths with exactly ' k ' coins ; Base cases ; If this subproblem is already solved ; ( m , n ) can be reached either through ( m - 1 , n ) or through ( m , n - 1 ) ; This function mainly initializes [ , ] dp [ ] and calls pathCountDPRecDP ( ) ; Driver Code
code: using System ; class GFG { static readonly int R = 3 ; static readonly int C = 3 ; static readonly int MAX_K = 100 ; static int [ , , ] dp = new int [ R , C , MAX_K ] ; static int pathCountDPRecDP ( int [ , ] mat , int m , int n , int k ) { if ( m < 0 n < 0 ) return 0 ; if ( m == 0 && n == 0 ) return ( k == mat [ m , n ] ? 1 : 0 ) ; if ( dp [ m , n , k ] != - 1 ) return dp [ m , n , k ] ; dp [ m , n , k ] = pathCountDPRecDP ( mat , m - 1 , n , k - mat [ m , n ] ) + pathCountDPRecDP ( mat , m , n - 1 , k - mat [ m , n ] ) ; return dp [ m , n , k ] ; } static int pathCountDP ( int [ , ] mat , int k ) { for ( int i = 0 ; i < R ; i ++ ) for ( int j = 0 ; j < C ; j ++ ) for ( int l = 0 ; l < MAX_K ; l ++ ) dp [ i , j , l ] = - 1 ; return pathCountDPRecDP ( mat , R - 1 , C - 1 , k ) ; } public static void Main ( String [ ] args ) { int k = 12 ; int [ , ] mat = { { 1 , 2 , 3 } , { 4 , 6 , 5 } , { 3 , 2 , 1 } } ; Console . WriteLine ( pathCountDP ( mat , k ) ) ; } }