Unique Paths — Grid Path Count DP

Problem

Count paths in m x n grid, moving only right or down.

Example: m=3, n=7 → 28

Approach — 2D DP (space-optimized to 1D)

dp[i][j] = dp[i-1][j] + dp[i][j-1]. Since each row only depends on previous row, use 1D rolling array.

Time: O(m*n) | Space: O(n)

Solutions

Python — 1D DP

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp=[1]*n
        for _ in range(1,m):
            for j in range(1,n):
                dp[j]+=dp[j-1]
        return dp[n-1]

Python — Math (combinatorics)

from math import comb
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m+n-2, n-1)

C++

class Solution {
public:
    int uniquePaths(int m, int n){
        vector<int> dp(n,1);
        for(int i=1;i<m;i++) for(int j=1;j<n;j++) dp[j]+=dp[j-1];
        return dp[n-1];
    }
};

Java

class Solution {
    public int uniquePaths(int m, int n){
        int[] dp=new int[n]; Arrays.fill(dp,1);
        for(int i=1;i<m;i++) for(int j=1;j<n;j++) dp[j]+=dp[j-1];
        return dp[n-1];
    }
}

Complexity

Time: O(m*n) | Space: O(n)