Unique Paths

Medium · 2-D Dynamic Programming

You are standing at the top-left corner of a grid with m rows and n columns. At each step you may move either one cell to the right or one cell down, and you want to reach the bottom-right corner. Count how many distinct sequences of moves accomplish this. Return that count as an integer.

Examples

Input:  m = 3, n = 7
Output: 28
Why:    There are 28 distinct step sequences of right and down moves that go from the top-left corner to the bottom-right corner of a 3 by 7 grid.

Input:  m = 3, n = 2
Output: 3
Why:    The only allowed moves are right and down, and there are exactly 3 distinct ways to arrange them to reach the opposite corner.

Input:  m = 1, n = 1
Output: 1
Why:    The start and end cell are the same, so there is exactly one (empty) path.

Constraints

1 <= m, n <= 100

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Unique Paths

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Unique Paths. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.