text: Number of ways to reach the end of matrix with non | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE #define n  3 NEW_LINE #define maxV  20 NEW_LINE using namespace std ; int dp [ n ] [ n ] [ maxV ] ; int v [ n ] [ n ] [ maxV ] ; int countWays ( int i , int j , int x , int arr [ ] [ n ] ) { 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 ] ; } int main ( ) { int arr [ n ] [ n ] = { { 1 , 2 , 1 } , { 1 , 1 , 0 } , { 2 , 1 , 1 } } ; cout << countWays ( 0 , 0 , arr [ 0 ] [ 0 ] , arr ) ; return 0 ; }