Number of ways to reach the end of matrix with non | Javascript implementation of the approach ; 3d array to store states of dp ; Array to determine whether a state has been solved before ; Function to return the count of required paths ; Base cases ; If a state has been solved before it won 't be evaluated again ; Recurrence relation ; Driver code
var n = 3 ; var maxV = 20 ; var dp = new Array ( n ) ; for ( var i = 0 ; i < n ; i ++ ) { dp [ i ] = new Array ( n ) ; for ( var j = 0 ; j < n ; j ++ ) { dp [ i ] [ j ] = new Array ( maxV ) ; } } var v = new Array ( n ) ; for ( var i = 0 ; i < n ; i ++ ) { v [ i ] = new Array ( n ) ; for ( var j = 0 ; j < n ; j ++ ) { v [ i ] [ j ] = new Array ( maxV ) ; } } function countWays ( i , j , x , arr ) { if ( i == n j == n ) return 0 ; x = ( x & arr [ i ] [ j ] ) ; if ( x == 0 ) return 0 ; if ( i == n - 1 && j == n - 1 ) return 1 ; if ( v [ i ] [ j ] [ x ] ) return dp [ i ] [ j ] [ x ] ; v [ i ] [ j ] [ x ] = 1 ; dp [ i ] [ j ] [ x ] = countWays ( i + 1 , j , x , arr ) + countWays ( i , j + 1 , x , arr ) ; return dp [ i ] [ j ] [ x ] ; } var arr = [ [ 1 , 2 , 1 ] , [ 1 , 1 , 0 ] , [ 2 , 1 , 1 ] ] ; document . write ( countWays ( 0 , 0 , arr [ 0 ] [ 0 ] , arr ) ) ;