A robot on an m x n grid starts at top-left and can only move right or down. How many unique paths exist to the bottom-right?
Example
Input
3 7
Output
28
Reasoning
The input 3 7 means m=3 rows and n=7 columns. The robot goes from the top-left cell to the bottom-right cell, one step right or down at a time.
Any route must drop m−1=2 rows and cross n−1=6 columns, so every path is exactly 8 moves long: 2 downs and 6 rights. Two paths differ only in when the downs happen.
A tiny case makes this concrete: on a 3×2 grid the routes are D D R, D R D and R D D, so there are 3.
For the sample, group the paths by the columns where the two downs happen. Both downs in the same column: 7 choices. Downs in two different columns: 27×6=21 pairs. Total 7+21=28.
The output 28 is a single integer count. Notice that a 1×1 grid gives 1: the robot is already at the goal, and the empty route still counts as one path.
The "Unique Paths" problem is a classic example of a combinatorial problem that can be solved using dynamic programming. To understand this problem, it's essential to have a basic grasp of combinatorics, which is the study of counting and arranging objects in various ways. In this case, we're counting the number of unique paths a robot can take to reach the bottom-right corner of a grid. The robot can only move right or down, which means that each path is a sequence of right and down moves.
The key concept here is that the number of unique paths to a cell is the sum of the number of unique paths to the cell above it and the cell to its left. This is because the robot can only reach a cell by moving down from the cell above or right from the cell to its left. This idea is the foundation of the dynamic programming approach, which involves breaking down a problem into smaller sub-problems, solving each sub-problem only once, and storing the solutions to sub-problems to avoid redundant computation.
To solve this problem, you should also be familiar with grid traversal and memoization, which are common techniques used in dynamic programming. Grid traversal involves iterating over a grid and performing operations on each cell, while memoization involves storing the results of expensive function calls so that they can be reused instead of recomputed.
Algorithm/Approach
The general approach to solving this type of problem is to use a bottom-up dynamic programming approach. This involves creating a 2D array, dp, where dp[i][j] represents the number of unique paths to the cell at position (i, j). The algorithm starts by initializing the first row and column of the dp array, since there is only one way to reach each cell in the first row (by always moving right) and each cell in the first column (by always moving down).
PRO
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
PRO
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.