Leetcode - Unique Paths

Question

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Idea

• This is a fairly basic 2D Dynamic Programming question, where here, we are memoizing how many ways we can get to any particular (i, j) location, since each one of these locations will be contributing towards going to the bottom right corner
• We use a recursive solution, first checking if we have visited our (i, j) before, then if we are out of index, then if we are at our target location
• Then we iterate through our possible directions (either down, or right) and add the result of both to our total, then we store that total in our (i, j) cache and return that result

Solution