Unique Paths: A Dynamic Programming Approach

The "Unique Paths" problem is a fundamental dynamic programming challenge that involves finding the number of distinct paths from the top-left corner to the bottom-right corner in a grid.

Problem Statement

Given a m x n grid, find the number of unique paths that the robot can take to reach the bottom-right corner from the top-left corner. The robot can only move either down or right at any point in time.

Example

• Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
  1. Right -> Right -> Down
  2. Right -> Down -> Right
  3. Down -> Right -> Right

Dynamic Programming Solution

Breaking Down the Solution

• Initialize dp Array: Create a m x n dp array and initialize all elements to 1. Each cell represents the number of paths to reach that cell.
• Dynamic Programming Iteration: Iterate through the grid, and for each cell, calculate the number of paths by adding the paths from the top and left cells.
• Return Total Unique Paths: The value in dp[m - 1][n - 1] gives the total number of unique paths to reach the bottom-right corner.

Conclusion

The Unique Paths problem is an excellent example of dynamic programming applied to grid-based problems. It demonstrates how to incrementally build up solutions and is essential for understanding pathfinding and navigation within grids in various applications.

Rust Solution

The nested vec![vec![1i32; n]; m] macro allocates and pre-fills the entire m × n grid with 1 in a single expression, so there is no separate initialisation loop as in the other languages. The 1i32 suffix pins the element type, which lets the function return i32 while the dimensions and loop counters stay usize (m: usize, n: usize) — the type Rust requires for slice indexing. The trailing dp[m - 1][n - 1] is the return value: as the final expression of the block it needs no return keyword and no semicolon.

Go Solution

Go has no nested-fill literal, so make([][]int, m) allocates only the outer slice and each row gets its own make([]int, n) inside the for i := range dp loop. Because make zero-initialises every int to 0, the inner range loop must explicitly run dp[i][j] = 1 to seed the grid — there is no one-shot fill like Rust's vec!. The grouped signature func uniquePaths(m, n int) int and the dp[m-1][n-1] return keep the rest close to the JavaScript original.