Unique Paths in Grid DP in DSA Typescript - Build from Scratch

Unique Paths in Grid DP

📖 Scenario: Imagine you are helping a robot find how many ways it can move from the top-left corner to the bottom-right corner of a grid. The robot can only move right or down.

🎯 Goal: Build a program that calculates the number of unique paths the robot can take in a grid of given size using dynamic programming.

📋 What You'll Learn

Create a 2D array to represent the grid

Use a variable to store the number of rows and columns

Fill the grid with the number of ways to reach each cell

Print the number of unique paths to the bottom-right cell

💡 Why This Matters

🌍 Real World

Robots and automated systems often need to find paths in grids or maps. This method helps calculate how many ways a robot can reach a destination.

💼 Career

Understanding dynamic programming and grid traversal is useful in software development roles involving algorithms, robotics, game development, and pathfinding problems.

1

Create the grid size variables

Create two variables called rows and cols and set them to 3 and 3 respectively.

DSA Typescript

// Your code here

Hint

Use const to create variables for rows and columns with values 3.

2

Initialize the 2D grid array

Create a 2D array called dp with rows arrays each containing cols zeros.

DSA Typescript

const rows = 3;
const cols = 3;
// Your code here

Hint

Use Array.from with a mapping function to create a 2D array filled with zeros.

3

Fill the grid with unique path counts

Use nested for loops with variables r and c to fill dp. Set dp[r][c] to 1 if r or c is zero. Otherwise, set dp[r][c] to dp[r-1][c] + dp[r][c-1].

DSA Typescript

const rows = 3;
const cols = 3;
const dp: number[][] = Array.from({ length: rows }, () => Array(cols).fill(0));
// Your code here

Hint

Use two loops to fill the grid. The first row and column are always 1. Other cells are sum of top and left cells.

4

Print the number of unique paths

Print the value of dp[rows - 1][cols - 1] using console.log.

DSA Typescript

const rows = 3;
const cols = 3;
const dp: number[][] = Array.from({ length: rows }, () => Array(cols).fill(0));

for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
        if (r === 0 || c === 0) {
            dp[r][c] = 1;
        } else {
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
        }
    }
}
// Your code here

Hint

Print the bottom-right cell value which holds the total unique paths.