Unique Paths in a Grid

You are given two positive integers m and n representing the dimensions of a grid. Starting from the top-left corner, you need to find the number of unique paths to reach the bottom-right corner. In each step, you can only move either right or down.

The number of unique paths can be computed using dynamic programming by initializing the first row and first column with 1’s (since there is only one way to reach any cell in the first row or column) and then filling in each cell with the sum of its top and left neighbors.

The recurrence relation is given by:

\( dp[i][j] = dp[i-1][j] + dp[i][j-1] \)

where \( dp[i][j] \) denotes the number of unique paths to reach cell \( (i, j) \) in the grid. The answer is \( dp[m-1][n-1] \).

inputFormat

The input consists of a single line with two space-separated integers m and n (1 ≤ m, n ≤ 100) representing the number of rows and columns respectively.

outputFormat

Output a single integer which is the number of unique paths from the top-left corner to the bottom-right corner.

3 7

28