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).
m = 3, n = 410def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]function uniquePaths(m, n) {
const dp = Array.from({ length: m }, () => new Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 1));
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}Explanation
A robot moves from the top-left to the bottom-right of an m × n grid, stepping only right or down. We count the distinct paths with a DP table where dp[i][j] = number of ways to reach cell (i, j).
Since the robot can only come from above or from the left, the recurrence is dp[i][j] = dp[i-1][j] + dp[i][j-1] — add up the ways to reach each of those two neighbors.
The entire first row and first column are all 1: there is exactly one straight-line way to reach any cell on the top edge (all rights) or the left edge (all downs). That is why the table is initialized to all 1s before filling the interior.
We then sweep the inner cells left-to-right, top-to-bottom, and the bottom-right cell holds the final count.
Example: m = 3, n = 4. The robot makes 2 down-moves and 3 right-moves in some order, giving C(5, 2) = 10 paths — exactly what dp[2][3] works out to.