Number of paths with exactly k coins | A Naive Recursive PHP program to count paths with exactly ' k ' coins ; Recursive function to count paths with sum k from ( 0 , 0 ) to ( m , n ) ; Base cases ; ( m , n ) can be reached either through ( m - 1 , n ) or through ( m , n - 1 ) ; A wrapper over pathCountRec ( ) ; Driver program
< ? php $ R = 3 ; $ C = 3 ; function pathCountRec ( $ mat , $ m , $ n , $ k ) { if ( $ m < 0 or $ n < 0 ) return 0 ; if ( $ m == 0 and $ n == 0 ) return ( $ k == $ mat [ $ m ] [ $ n ] ) ; return pathCountRec ( $ mat , $ m - 1 , $ n , $ k - $ mat [ $ m ] [ $ n ] ) + pathCountRec ( $ mat , $ m , $ n - 1 , $ k - $ mat [ $ m ] [ $ n ] ) ; } function pathCount ( $ mat , $ k ) { global $ R , $ C ; return pathCountRec ( $ mat , $ R - 1 , $ C - 1 , $ k ) ; } $ k = 12 ; $ mat = array ( array ( 1 , 2 , 3 ) , array ( 4 , 6 , 5 ) , array ( 3 , 2 , 1 ) ) ; echo pathCount ( $ mat , $ k ) ; ? >