class Solution {
	private static HashMap<String, Integer> map = new HashMap<>();

	public int uniquePaths(int m, int n) {
		map = new HashMap<>();
		if (m == 0 && n == 0) {
			return 0;
		}
		return minPathSum(0, 0, m, n);
	}

	public int minPathSum(int i, int j, int m, int n) {
		int paths = 0;
		String key = i + "" + j;
		if (map.containsKey(key)) {
			return map.get(key);
		}
		if (i == m - 1 && j == n - 1) {
			return 1;
		}
		if (i < m - 1) {
			paths += minPathSum(i + 1, j, m, n);
		}

		if (j < n - 1) {
			paths += minPathSum(i, j + 1, m, n);
		}
		map.put(key, paths);
		return paths;
	}
}