Number of ways to reach the end of matrix with non | Java 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
class GFG { static int n = 3 ; static int maxV = 20 ; static int [ ] [ ] [ ] dp = new int [ n ] [ n ] [ maxV ] ; static int [ ] [ ] [ ] v = new int [ n ] [ n ] [ maxV ] ; static int countWays ( int i , int j , int x , int 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 ] == 1 ) { 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 ] ; } public static void main ( String [ ] args ) { int arr [ ] [ ] = { { 1 , 2 , 1 } , { 1 , 1 , 0 } , { 2 , 1 , 1 } } ; System . out . println ( countWays ( 0 , 0 , arr [ 0 ] [ 0 ] , arr ) ) ; } }