Similar to above if direction is column
dp [ i ] [ j ] [ k ] [ d ] = countPathsUtil ( i - 1 , j , k , d ) + countPathsUtil ( i , j - 1 , k - 1 , not d ) NEW_LINE return dp [ i ] [ j ] [ k ] [ d ] NEW_LINE