Count number of paths with at | Java program to count number of paths with maximum k turns allowed ; table to store results of subproblems ; Returns count of paths to reach ( i , j ) from ( 0 , 0 ) using at - most k turns . d is current direction d = 0 indicates along row , d = 1 indicates along column . ; If invalid row or column indexes ; If current cell is top left itself ; If 0 turns left ; If direction is row , then we can reach here only if direction is row and row is 0. ; If direction is column , then we can reach here only if direction is column and column is 0. ; If this subproblem is already evaluated ; If current direction is row , then count paths for two cases 1 ) We reach here through previous row . 2 ) We reach here through previous column , so number of turns k reduce by 1. ; Similar to above if direction is column ; This function mainly initializes ' dp ' array as - 1 and calls countPathsUtil ( ) ; If ( 0 , 0 ) is target itself ; Initialize ' dp ' array ; Recur for two cases : moving along row and along column return countPathsUtil ( i - 1 , j , k , 1 ) + Moving along row countPathsUtil ( i , j - 1 , k , 0 ) ; Moving along column ; Driver Code
import java . util . * ; class GFG { static int MAX = 100 ; static int [ ] [ ] [ ] [ ] dp = new int [ MAX ] [ MAX ] [ MAX ] [ 2 ] ; static int countPathsUtil ( int i , int j , int k , int d ) { if ( i < 0 j < 0 ) return 0 ; if ( i == 0 && j == 0 ) return 1 ; if ( k == 0 ) { if ( d == 0 && i == 0 ) return 1 ; if ( d == 1 && j == 0 ) return 1 ; return 0 ; } if ( dp [ i ] [ j ] [ k ] [ d ] != - 1 ) return dp [ i ] [ j ] [ k ] [ d ] ; if ( d == 0 ) return dp [ i ] [ j ] [ k ] [ d ] = countPathsUtil ( i , j - 1 , k , d ) + countPathsUtil ( i - 1 , j , k - 1 , d == 1 ? 0 : 1 ) ; return dp [ i ] [ j ] [ k ] [ d ] = countPathsUtil ( i - 1 , j , k , d ) + countPathsUtil ( i , j - 1 , k - 1 , d == 1 ? 0 : 1 ) ; } static int countPaths ( int i , int j , int k ) { if ( i == 0 && j == 0 ) return 1 ; for ( int p = 0 ; p < MAX ; p ++ ) { for ( int q = 0 ; q < MAX ; q ++ ) { for ( int r = 0 ; r < MAX ; r ++ ) for ( int s = 0 ; s < 2 ; s ++ ) dp [ p ] [ q ] [ r ] [ s ] = - 1 ; } } } public static void main ( String [ ] args ) { int m = 3 , n = 3 , k = 2 ; System . out . println ( " Number ▁ of ▁ paths ▁ is ▁ " + countPaths ( m - 1 , n - 1 , k ) ) ; } }