62. Unique Paths

Problem

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

Problem Summary

A robot is located at the top-left corner of an m x n grid (the starting point is marked as “Start” in the diagram below). The robot can only move one step down or right each time. The robot is trying to reach the bottom-right corner of the grid (marked as “Finish” in the diagram below). How many different paths are there in total?

Solution Approach

• This is a simple DP problem. Output the number of ways to move from the top-left corner to the bottom-right corner on the map.
• Since the robot can only move right and down, the number of ways for the first row and the first column of the map is 1. The number of ways to reach any point on the map is dp[i][j] = dp[i-1][j] + dp[i][j-1]

Code

package leetcode

func uniquePaths(m int, n int) int {
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if i == 0 || j == 0 {
				dp[i][j] = 1
				continue
			}
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[n-1][m-1]
}