Imagine a scenario where an adventurous little robot, named Robi, has a mission to traverse a grid with m rows and n columns and reach a treasure box placed at $grid[m-1][n-1]$. Robi starts the journey from its home in the top-left corner of the grid, $grid[0][0]$. However, it faces a constraint that at any given time, it can only move in either of the two directions: downward or to the right.

Given the two integers, m and n, return the total number of unique paths that Robi can take from the grid's top-left corner to reach the bottom-right corner of the grid.

Constraints:

• 1 $\leq$ m, n $\leq$ 100

So far, you’ve probably brainstormed some approaches on how to solve this problem. Let’s explore some of these approaches and figure out which one to follow while considering time complexity and any implementation constraints.

The naive approach uses recursion to consider every possible path that the robot can take from the top-left corner of the grid to the bottom-right corner. The algorithm begins with the top-left corner and explores two branches: moving right and moving down. This process continues recursively, generating further branches for each valid move. Eventually, the recursion reaches the base cases:

• If the robot reaches the bottom-right corner, a single path is counted.

• If it goes out of bounds or reaches an edge, such a path is not counted.

The algorithm sums up the number of paths obtained through these recursive explorations and returns this number as the total number of unique paths.

Since this approach recalculates the overlapping subproblems, it becomes inefficient as the grid size grows, resulting in exponential time complexity. The robot takes a total of $m + n - 2$ steps to go from the top-left corner to the bottom-right corner, which results in $2^{m + n - 2}$ number of nodes in the recursion tree. Overall, the time complexity for this naive approach is $O(2^{m + n})$. The maximum depth of the recursion stack corresponds to the height of the recursion tree, which is $m + n - 2$, so the overall space complexity for this approach is $O(m + n)$.

Let’s look at the bottom-up dynamic programming approach to solve this problem. In this approach, solutions to smaller subproblems are stored in a table as they are computed, and these solutions are then used to solve larger subproblems until the main problem is solved.

For this specific problem, we start with solving the simplest cases along the first row and first column. These are straightforward because there's only one way to reach them. We save these solutions and then use them to find solutions for other cells by adding up the values from the cell above and the cell to the left. This process continues until we calculate the total unique paths to the bottom-right cell. The value in the bottom-right cell will represent the total number of unique paths. This approach avoids unnecessary calculations and is more efficient.