Unique Paths

Medium

The problem

A grid has m rows and n columns. A robot starts at the top-left cell and can only move right or down. Return how many different paths lead to the bottom-right cell.

Example 1
Input: m = 3, n = 7
Output: 28
Example 2
Input: m = 3, n = 2
Output: 3
Right-Down-Down, Down-Right-Down and Down-Down-Right.

Limits

1 ≤ m, n ≤ 100
The answer fits in a 32-bit integer

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

You can only reach a cell from the one above or the one to its left.

The idea

dp[r][c] = dp[r−1][c] + dp[r][c−1] with the first row and column all 1; one row of memory is enough.

Target: O(m·n) time, O(n) space

Go function shape

func uniquePaths(m int, n int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// UniquePaths: robot moves right or down on an m×n grid.
// dp[c] holds the ways to reach column c of the current row; it is updated row by row in one slice.
func UniquePaths(m, n int) int {
	dp := make([]int, n)
	for c := range dp {
		dp[c] = 1 // top row: only one way to reach each cell
	}
	for r := 1; r < m; r++ {
		for c := 1; c < n; c++ {
			dp[c] += dp[c-1] // from above (old dp[c]) + from the left (new dp[c-1])
		}
	}
	return dp[n-1]
}

Read the lesson: 2-D Dynamic Programming