Problem Statement
Given a 2dimensional grid of size m x n
(where m
is the number of rows and n
is the number of columns), you need to find out the number of unique paths from the topleft corner to the bottomright corner. The constraints are that you can only move either right or down at any point in time.
Examples

Example 1:
 Input: 3, 3
 Expected Output: 6
 Justification: The six possible paths are:
 Right, Right, Down, Down
 Right, Down, Right, Down
 Right, Down, Down, Right
 Down, Right, Right, Down
 Down, Right, Down, Right
 Down, Down, Right, Right

Example 2:
 Input: 3, 2
 Expected Output: 3
 Justification: The three possible paths are:
 Right, right, down
 Right, down, right
 Down, right, right

Example 3:
 Input: 2, 3
 Expected Output: 3
 Justification: The three possible paths are:
 Down, right, right
 Right, down, right
 Right, right, down
Solution
The unique paths problem can be approached using a dynamic programming solution. Essentially, the idea is to think of the grid as a graph where each cell is a node. Given we can only move right or down, the number of ways to reach a cell is the sum of the number of ways to reach the cell above it and the cell to its left. By breaking down the problem in this way, we can iteratively compute the number of paths to reach any cell, starting from the topleft and working our way to the bottomright of the grid.

Initialization:
 Create a 2dimensional array
dp
of sizem x n
initialized to zero. This array will store the number of unique paths to reach each cell.
 Create a 2dimensional array

Boundary Cases:
 All cells in the first row can only be reached by moving right from the topleft corner. So, the number of unique paths for all cells in the first row will be 1.
 Similarly, all cells in the first column can only be reached by moving downwards from the topleft corner. So, the number of unique paths for all cells in the first column will be 1.

Filling the Table:
 For each remaining cell, the number of unique paths to that cell is the sum of the number of paths from the cell above it and the cell to the left of it. This is because we can only move right or down.

Result:
 The bottomright cell will contain the total number of unique paths from the topleft corner to the bottomright corner.
Algorithm Walkthrough
Using the input from Example 1 (2, 2):
 Initialize a 2x2 matrix
dp
with all zeros.0 0 0 0
 Fill the first row and first column with 1s.
1 1 1 0
 For cell dp[1][1], add values from cell above (dp[0][1]) and cell to the left (dp[1][0]).
1 1 1 2
 The bottomright cell (dp[1][1]) contains the number of unique paths: 2.
Code
Complexity Analysis
 Time Complexity: O(m * n)  We are processing each cell once.
 Space Complexity: O(m * n)  Due to the 2D dp array.