m x n grid and may only move right or down. Return the number of distinct paths from the top-left corner to the bottom-right corner.Count Unique Paths
L8 Hard Dynamic Programming
Concept
On a grid, the number of ways to reach a cell is the sum of the ways to reach the cell above it and the cell to its left — a classic DP on a grid.
A robot starts at the top-left of an
Examples
▸ m = 3, n = 7
→ 28
▸ m = 3, n = 2
→ 3
▸ m = 3, n = 3
→ 6
Progressive Hints
Hint 1 · Nudge
Every cell counts the paths from above plus the paths from the left.
Hint 2 · Plan
All cells in the first row and the first column have exactly 1 path. Every other cell's count is the sum of the cell above it and the cell to its left. Fill the grid row by row.
Hint 3 · Approach
Grid of m rows by n columns, first row and column set to 1. For each inner cell, set it to the cell above plus the cell to the left. Return the bottom-right corner.
All hints are out. Take a breath and give it a shot.
Output
// Run your code to see the output here.