Unique Paths - https://leetcode.com/problems/unique-paths/description/

gistfile1.txt

class Solution {
    public int uniquePaths(int m, int n) {
       // m is columns
       // n is rows
      
      if (m < 1 || n < 1) {
        return 0;
      }
      
      if (m == 1 && m == 1) {
        return 1;
      }
      
      int count = recursiveTraverse(0, 0, n - 1, m - 1, 0);
      return count;
    }
  
    private int recursiveTraverse(int i, int j, final int maxI, final int maxJ, int count) {
      if (i == maxI && j == maxJ) {
        return (count + 1);
      }
      
      if (i > maxI || j > maxJ) {
        return 0;
      }
      
      int countRight = recursiveTraverse(i, j + 1, maxI, maxJ, count);
      int countDown = recursiveTraverse(i + 1, j, maxI, maxJ, count);
      return countRight + countDown;
    }
}

Dynamic programming solution:

class Solution {
    public int uniquePaths(int m, int n) {
       // m is columns
       // n is rows
      
      if (m < 1 || n < 1) {
        return 0;
      }
      
      if (m == 1 && m == 1) {
        return 1;
      }
      
      // Max is 100x100
      if (m > 100 || n > 100) {
        throw new IllegalArgumentException();
      }
      
      // backtrack matrix
      int[][] visited = new int[n][m];
      
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          if (i == 0 && j == 0) {
            visited[i][j] = 1;
          } else {
            if (i == 0) {
              visited[i][j] = visited[i][j-1];
            } else if (j == 0) {
              visited[i][j] = visited[i-1][j];
            } else {
              visited[i][j] = visited[i][j-1] + visited[i-1][j];
            }
          } 
        }
      }
      
      return visited[n-1][m-1];
    }
}