Unique Paths

Medium

Python

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]

Java

public int uniquePaths(int m,int n){
    int[][] dp=new int[m][n];
    for(int[] row:dp) Arrays.fill(row,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];
}

Key Insight

Grid DP. Python list comprehension vs Arrays.fill per row.

Python → Java Differences

[[1]*n for _ in range(m)] vs Arrays.fill
Grid DP identical
sum of top+left

Python

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]

Java

public int uniquePaths(int m,int n){
    int[][] dp=new int[m][n];
    for(int[] row:dp) Arrays.fill(row,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];
}

Algorithm Steps

1. Initialize with 1s
2. Sum from top and left

← Previous All Dynamic Programming Next →