Unique Paths

Problem Statement

You’re a robot in an m×n grid, starting at top-left, aiming for bottom-right, moving only right or down. How many unique paths exist? This medium-level DP puzzle is a maze-runner’s delight—count your ways to the finish!

Example

Input: m = 3, n = 2

Output: 3 (R-D, D-R, R-D)

Input: m = 7, n = 3

Output: 28

Input: m = 1, n = 1

Output: 1 (no moves needed)

Code

public 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];
    }
}
            

def 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[m-1][n-1]

# Example usage
print(unique_paths(3, 2))  # 3
print(unique_paths(7, 3))  # 28
            

function uniquePaths(m, n) {
    let dp = Array(m).fill().map(() => 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];
}

// Example usage
console.log(uniquePaths(3, 2));  // 3
console.log(uniquePaths(7, 3));  // 28
            

Explanation

• DP Insight: dp[i][j] = ways to reach (i,j) = sum of up and left paths.
• Steps: Edges are 1 (only one way), inner cells sum prior paths.
• Flow Example (3×2): dp[0][1]=1, dp[1][1]=2, dp[2][1]=3.
• Why It Works: Combinatorial addition of all valid moves.

Note