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

function uniquePaths(m, n) {
  const dp = Array.from(Array(m), () => new Array(n).fill(1));

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }

  return dp[m - 1][n - 1];
}

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.