Robot Paths in a Grid

You are given an m x n grid. A robot is located at the top-left corner of the grid and wants to reach the bottom-right corner. The robot can only move right or down at any point in time.

Your task is to compute the number of unique paths the robot can take to reach the end of the grid. This problem can be solved using dynamic programming. In mathematical terms, if we denote the number of unique paths from the top-left to cell (i, j) by dp[i][j], then the following recurrence holds:

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

with the base cases:

[ dp[i][0] = 1, \quad dp[0][j] = 1 ]

for all valid i and j. The final answer is given by dp[m-1][n-1].

inputFormat

The input consists of two positive integers m and n separated by space (or newline), representing the number of rows and columns of the grid respectively.

outputFormat

Output a single integer, which is the number of unique paths the robot can take to reach the bottom-right corner.

1 1

1