# 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]
```