Unique Paths Problem

A robot is located at the top-left corner of a m x n grid.

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

How many possible unique paths are there?

Example 1

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2

Input: m = 7, n = 3
Output: 28

Solutions

Dynamic Programming

Let's treat BOARD[i][j] as our sub-problem.

Since we have restriction of moving only to the right and down we might say that number of unique paths to the current cell is a sum of numbers of unique paths to the cell above the current one and to the cell to the left of current one.

BOARD[i][j] = BOARD[i - 1][j] + BOARD[i][j - 1]

Base cases are:

BOARD[0][any] = 1; // only one way to reach any top slot.
BOARD[any][0] = 1; // only one way to reach any slot in the leftmost column.

Implementation

class UniquePaths:
    def solve(self, rows, cols):
        board = [[0 for j in range(cols)] for i in range(rows)]
        for x in range(rows):
            for y in range(cols):
                if x==0 or y==0:
                    board[x][y] = 1
                else:
                    board[x][y] = board[x-1][y] + board[x][y-1]
        return board[x][y]