Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Unique Paths

LeetCode #62Medium
Grid DP · dp[i][j] = dp[i−1][j] + dp[i][j−1]

A robot starts at the top-left corner of an m x n grid and may only move right or down. Return the number of distinct paths it can take to reach the bottom-right corner.

Asked atAmazonGoogleBloomberg
step 1 / 9
3 × 4 grid · dp = #paths to here
·
·
·
·
·
·
·
·
·
·
·
·
Grid DP (tabulation)
▸
1dp = R × C grid
2fill top row and left column with 1
3for i in 1..R−1: for j in 1..C−1:
4    dp[i][j] = dp[i−1][j] + dp[i][j−1]
5 
6return dp[R−1][C−1]
state
  • grid3×4
  • statedp[i][j] = #paths to (i,j)

line 1A robot starts at the top-left and reaches the bottom-right, moving only RIGHT or DOWN. How many distinct paths? Define dp[i][j] = number of ways to reach cell (i, j). The answer is dp at the bottom-right.