Solution: Unique Paths

Statement

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

Solution

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.

Naive approach

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+}$ ...