Unique Paths

Definition

Definition

The Unique Paths Algorithm calculates the number of unique paths from the top-left corner to the bottom-right corner of a grid, moving only down or right

Explanation

It utilizes dynamic programming to compute the number of unique paths. It starts with initializing a 2D array to store the number of unique paths for each cell. Then, it iterates through each cell of the grid, calculating the number of unique paths to reach that cell by summing the paths from the cell above and the cell to the left. Finally, it returns the value in the bottom-right corner, which represents the total number of unique paths

Guidance

• Initialize a 2D array grid of size m x n, where grid[i][j] represents the number of unique paths to reach cell [i, j]
• Set grid[0][0] to 1, as there's only one way to reach the starting cell
• Iterate through each cell in the grid
  • for each cell [i, j], update grid[i][j]=grid[i-1][j] + grid[i][j-1] (if they exist)
• Return grid[m-1][n-1], which represents the number of unique paths from the top-left corner to the bottom-right corner

Tips

• utilize memoization or dynamic programming to optimize computation time and space
• be mindful of integer overflow when dealing with large grid

Practice

Practice

uniquePaths(m, n):
  # Initialize a 2D array to store the number of unique paths
  grid = [[0] * n for _ in range(m)]

  # Set the starting point to 1
  grid[0][0] = 1

  # Iterate through each cell
  for i from 0 to m-1:
    for j from 0 to n-1:
      # Update the number of unique paths for the current cell
      if i > 0:
        grid[i][j] += grid[i-1][j]
      if j > 0:
        grid[i][j] += grid[i][j-1]

  # Return the number of unique paths to the bottom-right corner
  return grid[m-1][n-1]

Solution

package main

func uniquePaths(m int, n int) int {
func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}

public class UniquePaths {

  public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
      dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
      dp[0][j] = 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];
  }
}

function uniquePaths(m, n) {
  const dp = Array.from(Array(m), () => 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];
}

fun uniquePaths(m: Int, n: Int): Int {
    val dp = Array(m) { IntArray(n) { 1 } }
    for (i in 1 until m) {
        for (j in 1 until n) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
}

def uniquePaths(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[-1][-1]

fn unique_paths(m: i32, n: i32) -> i32 {
    let mut dp = vec![vec![1; n as usize]; m as usize];
    for i in 1..m as usize {
        for j in 1..n as usize {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    dp[(m - 1) as usize][(n - 1) as usize]
}

function uniquePaths(m: number, n: number): number {
  const dp: number[][] = Array.from(Array(m), () => 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];
}