Count number of ways to reach a given score in a Matrix | PHP implementation of the approach ; To store the states of dp ; To check whether a particular state of dp has been solved ; Function to find the ways using memoization ; Base cases ; If required score becomes negative ; If current state has been reached before ; Set current state to visited ; Driver code
< ? php $ n = 3 ; $ MAX = 30 ; $ dp = array ( $ n , $ n , $ MAX ) ; $ v = array ( $ n , $ n , $ MAX ) ; function findCount ( $ mat , $ i , $ j , $ m ) { if ( $ i == 0 && $ j == 0 ) { if ( $ m == $ mat [ 0 ] [ 0 ] ) return 1 ; else return 0 ; } if ( $ m < 0 ) return 0 ; if ( $ i < 0 $ j < 0 ) return 0 ; if ( $ v [ $ i ] [ $ j ] [ $ m ] ) return $ dp [ $ i ] [ $ j ] [ $ m ] ; $ v [ $ i ] [ $ j ] [ $ m ] = true ; $ dp [ $ i ] [ $ j ] [ $ m ] = findCount ( $ mat , $ i - 1 , $ j , $ m - $ mat [ $ i ] [ $ j ] ) + findCount ( $ mat , $ i , $ j - 1 , $ m - $ mat [ $ i ] [ $ j ] ) ; return $ dp [ $ i ] [ $ j ] [ $ m ] ; } $ mat = array ( array ( 1 , 1 , 1 ) , array ( 1 , 1 , 1 ) , array ( 1 , 1 , 1 ) ) ; $ m = 5 ; echo ( findCount ( $ mat , $ n - 1 , $ n - 1 , $ m ) ) ;