A robot starts in the top left corner of an m by n grid. It can only move right or down, so count the number of different paths to the bottom right corner.
DSA Animator › DSA Revision › Dynamic Programming › Unique Paths
Remember: paths into a cell equal the sum of paths into the cells that lead to it. One row of memory is enough. The video solves Unique Paths (LeetCode 62, Easy) with the 2D Grid DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive Unique Paths animation.
A robot starts in the top left corner of an m by n grid. It can only move right or down, so count the number of different paths to the bottom right corner.
For a grid with 3 rows and 4 columns, there are 10 paths.
Exploring every path recursively visits the same cells many times. The number of paths explodes as the grid grows.
The robot can only enter a cell from above or from the left. So paths to a cell equals paths to the cell above plus paths to the cell on the left. Every cell in the first row or first column has exactly one path, a straight line. Fill the grid row by row, and the bottom right cell holds the answer.
The first row and first column are all 1. Row 1 column 1 is 1 plus 1, which is 2. Then row 1 continues with 3 and 4. Row 2 column 1 is 2 plus 1, which is 3. Then 3 plus 3 is 6, and 6 plus 4 is 10. So there are 10 unique paths.
In code, create a grid and fill the first row and first column with 1. For every other cell, add the value above and the value on the left. Return the bottom right cell. It's O of m times n time, or O of n space with a single row.
Remember: paths into a cell equal the sum of paths into the cells that lead to it. One row of memory is enough.