Unique paths

Math Dynamic Programming Combinatorics

66.6% acceptance

Jan 12, 2026

18263

492

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner. The test cases are generated so that the answer will be less than or equal to 2 * 109.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn unique_paths(m: i32, n: i32) -> i32 {
    let m = m as usize;
    let n = n as usize;
    let mut dp = vec![vec![0; n]; m];
    
    // Initialize first row and column
    for i in 0..m {
      dp[i][0] = 1;
    }
    for j in 0..n {
      dp[0][j] = 1;
    }
    
    // Fill the dp table
    for i in 1..m {
      for j in 1..n {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
      }
    }
    
    dp[m-1][n-1]
  }
}