Q:Say that you are a 2D grid traveler . you begin in the top left corner and your goal is to travel to bottom right corner . You can travel either down or right .
So how many ways you can travel through the grid?
So we can divide the problems into subproblems and the solution is same as the subproblems .By using recurrence relation we can use recursion to solve the problem . But if the input size is large then it will be time consuming to solve because the time complexity here is 2^(m+n).
So , we can use memorization technique.
Below is my java solution.
public class GridTravelerUsingRecursion {
private int gridTraveler(int m, int n, Map<String, Integer> memo) {
if (m == 0 || n == 0) {
return 0;
}
if (m == 1 || n == 1) {
return 1;
}
String key = m + "," + n;
if (memo.containsKey(key)) {
return memo.get(key);
} else {
int recursiveResult = gridTraveler(m - 1, n, memo) + gridTraveler(m, n - 1, memo);
memo.put(key, recursiveResult);
}
return memo.get(key);
}
public static void main(String[] args) {
int m = 20, n = 20;
Map<String, Integer> memo = new HashMap<>();
GridTravelerUsingRecursion grid = new GridTravelerUsingRecursion();
int result = grid.gridTraveler(m, n, memo);
System.out.println(result);
}
}
