Blind 75 · #59 · 2-D Dynamic Programming

Unique Paths

Medium2-D dynamic programmingTime O(m · n)Space O(n)

Unique Paths is a medium 2-D Dynamic Programming problem from the Blind 75. The key pattern is 2-d dynamic programming, and a good solution runs in O(m · n) time.

Problem

Count paths from the top-left to bottom-right of an m by n grid using only right and down moves.

Examples

Example 1

Input

{"m":3,"n":4}

Output

Example 2

Input

{"m":4,"n":5}

Output

Example 3

Input

{"m":2,"n":2}

Output

Approach

Each cell's path count is the count from above plus the count from the left; one rolling row is enough. A binomial coefficient also works.

Pattern	2-D dynamic programming
Time	O(m · n)
Space	O(n)

Watch out for

The first row and first column each have exactly one path.

Unique Paths

Problem

Examples

Example 1

Example 2

Example 3

Approach

Watch out for

More 2-D Dynamic Programming problems