/*
*  Problem: Lattice Paths - Pure Recursion
*
*  Prompt:  Count the number of unique paths to travel from the top left
*           corder to the bottom right corner of a lattice of M x N squares.
*
*           When moving through the lattice, one can only travel to the adjacent
*           corner on the right or down.
*
*  Input:   m {Integer} - rows of squares
*  Input:   n {Integer} - column of squares
*  Output:  {Integer}
*
*  Example: input: (2, 3)
*
*           (2 x 3 lattice of squares)
*            __ __ __
*           |__|__|__|
*           |__|__|__|
*
*           output: 10 (number of unique paths from top left corner to bottom right)
*
*  Resource: https://projecteuler.net/problem=15
*
*/

 

Using Recursion

class LatticePaths {
	public static int count;
  public static int compute(int m, int n) {
    // YOUR WORK HERE
	  count = 0;
   countLatticePaths(0, 0, m, n);
   return count;
  }
  
  private static void countLatticePaths(int i, int j, int m, int n) {
	  if(i == m && j == n) {
		  count++;
		  return;
	  }
	  
	  if(i > m || j > n)
		  return;
		  countLatticePaths(i+1, j, m, n);
		  countLatticePaths(i, j+1, m ,n);
  }
}

Using DP

private static int countLatticePathsDP(int m, int n) {
	  int[][] matrix = new int[m+1][n+1];
	  for(int i = 0; i < m; i++)
		  matrix[i][0] = 1;
	  for(int i = 0; i < n; i++)
		  matrix[0][i] = 1;
	  for(int i = 1; i <= m; i++) {
		  for(int j = 1; j <= n; j++) {
			  matrix[i][j] += matrix[i-1][j] + matrix[i][j-1];
		  }
	  }
	  return matrix[m][n];
  }