Count all possible paths from top left to bottom right of a mXn matrix | Returns count of possible paths to reach cell at row number m and column number n from the topmost leftmost cell ( cell at 1 , 1 ) ; Create a 2D table to store results of subproblems ; Count of paths to reach any cell in first column is 1 ; Count of paths to reach any cell in first column is 1 ; Calculate count of paths for other cells in bottom - up manner using the recursive solution ; By uncommenting the last part the code calculated the total possible paths if the diagonal Movements are allowed ; Driver Code
< ? php function numberOfPaths ( $ m , $ n ) { $ count = array ( ) ; for ( $ i = 0 ; $ i < $ m ; $ i ++ ) $ count [ $ i ] [ 0 ] = 1 ; for ( $ j = 0 ; $ j < $ n ; $ j ++ ) $ count [ 0 ] [ $ j ] = 1 ; for ( $ i = 1 ; $ i < $ m ; $ i ++ ) { for ( $ j = 1 ; $ j < $ n ; $ j ++ ) $ count [ $ i ] [ $ j ] = $ count [ $ i - 1 ] [ $ j ] + $ count [ $ i ] [ $ j - 1 ] + count [ i - 1 ] [ j - 1 ] ; } return $ count [ $ m - 1 ] [ $ n - 1 ] ; } echo numberOfPaths ( 3 , 3 ) ; ? >