Unique Paths — Step-by-Step Visualization

Algorithm Pattern

2D Dynamic Programming

Key Idea

Each cell's value is the sum of the paths from its right neighbor and its down neighbor, since the robot can only move in those directions to reach the goal.

Step-by-Step Approach

1. Create an m x n 2D array.
2. The goal cell (bottom-right) has 1 unique path to itself.
3. The bottom row and rightmost column cells only have one possible move to stay on track towards the goal, so they are initialized to 1.
4. Iterate backwards through the rest of the grid.
5. The transition formula is dp[r][c] = dp[r+1][c] + dp[r][c+1].

Common Gotchas

• Ensure you handle the grid boundaries by initializing the bottom row and right column first.
• The answer resides in the top-left cell dp[0][0].