Unique Paths - Python Solution

1. Introduction

"Unique Paths" is a classic problem in combinatorics and dynamic programming, often encountered in coding interviews. It involves finding the number of distinct paths a robot can take to traverse a grid from the top-left corner to the bottom-right corner, moving only down or right at each step. This problem tests one's ability to apply dynamic programming to solve combinatorial problems.

Problem

Given an m x n grid, with a robot initially located at the top-left corner (grid[0][0]) and the goal to reach the bottom-right corner (grid[m - 1][n - 1]), the task is to calculate the number of unique paths the robot can take. The robot can only move down or right at any point in time.

2. Solution Steps

1. Initialize a 2D array (or list of lists in Python) to store the number of ways to reach each cell.

2. Set the number of ways to reach the starting cell (top-left corner) as 1.

3. Iterate through the grid, updating the number of ways to reach each cell by summing the ways to reach the cell from the left and above.

4. The number of ways to reach a cell is the sum of ways to reach the cell directly above it and the cell to its left.

5. The bottom-right cell contains the total number of unique paths.

3. Code Program

def uniquePaths(m, n):
    # Create a 2D array with all elements initialized to 1
    dp = [[1 for _ in range(n)] for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[m-1][n-1]

# Example Usage
print(uniquePaths(3, 7))
print(uniquePaths(3, 2))

Output:

28
3

Explanation:

1. Dynamic Programming Grid: A 2D array dp is created to store the number of paths to each cell.

2. Initialization: The first row and column are initialized to 1 since there's only one way to reach cells in the first row/column.

3. Cell Update: Each cell's value is updated based on the sum of the paths from the cell above it and the cell to its left.

4. Iterative Calculation: The grid is filled iteratively, calculating the number of paths for each subsequent cell.

5. Result: The value in the bottom-right cell of the dp array gives the total number of unique paths.