Unique Paths
Problem Description
A robot is on an m x n grid at top-left corner, trying to reach bottom-right corner. The robot can only move right or down. How many unique paths exist?
Example 1:
Input: m=3, n=7
Output: 28
Example 2:
Input: m=3, n=2
Output: 3
DE Shaw Tier 3 — LC 62. Also practice LC 63 (with obstacles).
Math: C(m+n-2, m-1) — choose which steps go down.
DP O(m*n): dp[i][j] = dp[i-1][j] + dp[i][j-1]. Can optimize to O(n) space with single row.
Example Test Cases
Example 1
Input: [3,7]
Expected: 28
Example 2
Input: [3,2]
Expected: 3
Example 3
Input: [1,1]
Expected: 1
Example 4
Input: [5,5]
Expected: 70
Run your code to see the results