Unique Paths in a Grid

You are given a grid with m rows and n columns. Starting at the top-left corner, you can only move either right or down. Your task is to compute the number of unique paths to reach the bottom-right corner.

The solution can be approached using dynamic programming. If we denote by \(dp[i][j]\) the number of ways to reach cell \((i,j)\) then the recurrence is given by:

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

with the boundary conditions \(dp[i][0] = 1\) for all valid i and \(dp[0][j] = 1\) for all valid j. Note that if either m or n is zero, the grid is degenerate and there are no valid paths (i.e. the answer is 0).

inputFormat

The input consists of a single line with two space-separated integers m and n representing the dimensions of the grid.

outputFormat

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

2 3

3