LeetCode 62: Unique Paths - A Dynamic Programming Approach

LeetCode 62, "Unique Paths," is a classic problem that often serves as an excellent introduction to dynamic programming. It challenges us to find the number of unique paths a robot can take to reach the bottom-right corner of a m x n grid, starting from the top-left corner. The robot can only move either down or right at any point in time.

Problem Description

Imagine a robot positioned at the top-left cell (0,0) of a grid with m rows and n columns. The robot's goal is to reach the bottom-right cell (m-1, n-1). The only allowed moves are one step down or one step right. We need to calculate the total number of distinct paths the robot can take to reach its destination.

Let's visualize a simple 3 x 7 grid:

S . . . . . . . . . . . . . . . . . . . F

Where S is the start and F is the finish.

Dynamic Programming Approach

This problem has optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming.

Consider a cell (i, j) in the grid. To reach this cell, the robot must have come either from the cell directly above it (i-1, j) by moving down, or from the cell directly to its left (i, j-1) by moving right.

Therefore, the number of unique paths to reach (i, j) is the sum of unique paths to reach (i-1, j) and unique paths to reach (i, j-1).

Let dp[i][j] represent the number of unique paths to reach cell (i, j). The recurrence relation is: dp[i][j] = dp[i-1][j] + dp[i][j-1]

Base Cases:

For any cell in the first row (i=0), there's only one way to reach it: by moving right repeatedly from (0,0). So, dp[0][j] = 1.
For any cell in the first column (j=0), there's only one way to reach it: by moving down repeatedly from (0,0). So, dp[i][0] = 1.
The starting cell (0,0) has dp[0][0] = 1 path (it's already there).

We can build a 2D array (or even optimize space to a 1D array) to store these path counts.

Go Solution

Here's an implementation of the dynamic programming approach in Go:

DATA_NODE: go

func uniquePaths(m int, n int) int { // Create a 2D DP array initialized with 1s for the base cases dp := make([][]int, m) for i := range dp { dp[i] = make([]int, n) } // Initialize the first row and first column with 1s // since there's only one way to reach any cell in the first row/column // (by only moving right or only moving down respectively). for i := 0; i < m; i++ { dp[i][0] = 1 } for j := 0; j < n; j++ { dp[0][j] = 1 } // Fill the DP table for i := 1; i < m; i++ { for j := 1; j < n; j++ { dp[i][j] = dp[i-1][j] + dp[i][j-1] } } // The result is the value at the bottom-right corner return dp[m-1][n-1] }

Combinatorial Approach

Alternatively, this problem can be solved using a combinatorial approach. To reach the bottom-right corner of an m x n grid, the robot must make exactly m-1 'down' moves and n-1 'right' moves. The total number of moves will be (m-1) + (n-1).

The problem then reduces to finding the number of ways to arrange these m-1 down moves and n-1 right moves. This is a classic combinatorial problem: choosing m-1 positions for the 'down' moves (or n-1 positions for the 'right' moves) out of a total of (m-1) + (n-1) moves.

The formula for combinations is C(N, K) = N! / (K! * (N-K)!), where N is the total number of steps and K is the number of 'down' (or 'right') moves.

Go Solution (Combinatorial)

DATA_NODE: go

func uniquePathsCombinatorial(m int, n int) int { downMoves := m - 1 rightMoves := n - 1 totalSteps := downMoves + rightMoves // Choose the smaller of downMoves or rightMoves for k to minimize calculations k := downMoves if rightMoves < downMoves { k = rightMoves } var comb float64 = 1.0 // Formula: C(N, K) = (N/1) * ((N-1)/2) * ... * ((N-k+1)/k) // This avoids large factorial calculations by performing multiplications and divisions iteratively. for i := 1; i <= k; i++ { comb = comb * float64(totalSteps - i + 1) / float64(i) } return int(comb) }

Conclusion

The "Unique Paths" problem demonstrates the power of dynamic programming in breaking down a complex problem into simpler, overlapping subproblems. By carefully defining our state and recurrence relation, we can build up the solution efficiently. This particular problem also has a combinatorial solution using binomial coefficients, but the dynamic programming approach is often more intuitive for beginners to DP.