Number of ways to reach the end of matrix with non | Python3 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
n = 3 NEW_LINE maxV = 20 NEW_LINE dp = [ [ [ 0 for i in range ( maxV ) ] for i in range ( n ) ] for i in range ( n ) ] NEW_LINE v = [ [ [ 0 for i in range ( maxV ) ] for i in range ( n ) ] for i in range ( n ) ] NEW_LINE def countWays ( i , j , x , arr ) : NEW_LINE INDENT if ( i == n or j == n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT x = ( x & arr [ i ] [ j ] ) NEW_LINE if ( x == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( i == n - 1 and j == n - 1 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( v [ i ] [ j ] [ x ] ) : NEW_LINE INDENT return dp [ i ] [ j ] [ x ] NEW_LINE DEDENT v [ i ] [ j ] [ x ] = 1 NEW_LINE dp [ i ] [ j ] [ x ] = countWays ( i + 1 , j , x , arr ) + countWays ( i , j + 1 , x , arr ) ; NEW_LINE return dp [ i ] [ j ] [ x ] NEW_LINE DEDENT arr = [ [ 1 , 2 , 1 ] , [ 1 , 1 , 0 ] , [ 2 , 1 , 1 ] ] NEW_LINE print ( countWays ( 0 , 0 , arr [ 0 ] [ 0 ] , arr ) ) NEW_LINE