Number of paths with exactly k coins | A Dynamic Programming based javascript 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 Program to test above functions
var R = 3 ; var C = 3 ; var MAX_K = 100 ; var dp = Array ( R ) . fill ( ) . map ( ( ) => Array ( C ) . fill ( ) . map ( ( ) => Array ( MAX_K ) . fill ( 0 ) ) ) ; function pathCountDPRecDP ( mat , m , n , 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 ] ; } function pathCountDP ( mat , k ) { for ( i = 0 ; i < R ; i ++ ) for ( j = 0 ; j < C ; j ++ ) for ( l = 0 ; l < MAX_K ; l ++ ) dp [ i ] [ j ] [ l ] = - 1 ; return pathCountDPRecDP ( mat , R - 1 , C - 1 , k ) ; } var k = 12 ; var mat = [ [ 1 , 2 , 3 ] , [ 4 , 6 , 5 ] , [ 3 , 2 , 1 ] ] ; document . write ( pathCountDP ( mat , k ) ) ;