Grid Traveler Solution in Java

Problem Statement

Say that you are a traveler on a 2D grid. You begin in the top-left corner and you goal is to travel to the bottom-right corner.
You may only move down or right.

In how many ways can you travel to the goal on a grid with dimensions m*n ?

Write a function ‘gridTraveler(m,n)’ that calculate this.

Solution

package com.techbruiser.recursion;

import java.util.HashMap;
import java.util.Map;

public class GridTraveler {

	public static void main(String[] args) {
		
		System.out.println("gridTraveler(1,1) " + gridTraveler(1,1));//1
		System.out.println("gridTraveler(2,3) " + gridTraveler(2,3));//3
		System.out.println("gridTraveler(3,2) " + gridTraveler(3,2));//3
		System.out.println("gridTraveler(3,3) " + gridTraveler(3,3));//6
		System.out.println("gridTraveler(18,18) " + gridTraveler(18,18));//2333606220
	}
	
	
	/**
	 * Approach-1 Without Memorization
	 */ 
	/*static int gridTraveler(int m, int n) {
		if(m == 1 && n == 1) {
			return 1;
		}
		
		if(m == 0 || n== 0 ) {
			return 0;
		}
		
		return gridTraveler(m-1, n) + gridTraveler(m, n-1);
		
	}*/
	
	/**
	 * Approach-2 With Memorization
	 */
	static Map<String, Long> memorization = new HashMap<>();
	static Long gridTraveler(int m, int n) {
		String key = m+","+n;
		
		if(memorization.get(key) != null) {
			return memorization.get(key);
		}
		if(m == 1 && n == 1) {
			return (long) 1;
		}
		
		if(m == 0 || n== 0 ) {
			return (long) 0;
		}
		memorization.put(key, gridTraveler(m-1, n) + gridTraveler(m, n-1));
		return memorization.get(key);
		
	}
}