Count number of ways to reach a given score in a Matrix | Javascript 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
var n = 3 ; var MAX = 30 ; var dp = Array ( n ) ; for ( var i = 0 ; i < n ; i ++ ) { dp [ i ] = Array ( n ) ; for ( var j = 0 ; j < n ; j ++ ) { dp [ i ] [ j ] = Array ( MAX ) ; } } var v = Array ( n ) ; for ( var i = 0 ; i < n ; i ++ ) { v [ i ] = Array ( n ) ; for ( var j = 0 ; j < n ; j ++ ) { v [ i ] [ j ] = Array ( 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 ] ; } var mat = [ [ 1 , 1 , 1 ] , [ 1 , 1 , 1 ] , [ 1 , 1 , 1 ] ] ; var m = 5 ; document . write ( findCount ( mat , n - 1 , n - 1 , m ) ) ;