Unique Paths in Grid DP in DSA C

Mental Model

Count how many ways to move from top-left to bottom-right in a grid by only moving right or down.

Analogy: Imagine walking through a city grid where you can only go east or south. You want to know how many different routes you can take to reach your friend's house at the bottom-right corner.

Start (S) at top-left, End (E) at bottom-right:
S -> -> ->
↓   ↓   ↓
-> -> -> E
Only moves allowed: right (->) or down (↓)

Dry Run Walkthrough

Input: grid size: 3 rows x 3 columns

Goal: Find total unique paths from top-left (0,0) to bottom-right (2,2) moving only right or down

Step 1: Initialize first row with 1s because only one way to move right along top row

[1, 1, 1]
[0, 0, 0]
[0, 0, 0]

Why: Only one path to each cell in first row by moving right

Step 2: Initialize first column with 1s because only one way to move down along left column

[1, 1, 1]
[1, 0, 0]
[1, 0, 0]

Why: Only one path to each cell in first column by moving down

Step 3: Calculate paths for cell (1,1) by adding paths from top (0,1) and left (1,0)

[1, 1, 1]
[1, 2, 0]
[1, 0, 0]

Why: Paths to (1,1) = paths from above + paths from left

Step 4: Calculate paths for cell (1,2) by adding paths from top (0,2) and left (1,1)

[1, 1, 1]
[1, 2, 3]
[1, 0, 0]

Why: Paths to (1,2) = paths from above + paths from left

Step 5: Calculate paths for cell (2,1) by adding paths from top (1,1) and left (2,0)

[1, 1, 1]
[1, 2, 3]
[1, 3, 0]

Why: Paths to (2,1) = paths from above + paths from left

Step 6: Calculate paths for cell (2,2) by adding paths from top (1,2) and left (2,1)

[1, 1, 1]
[1, 2, 3]
[1, 3, 6]

Why: Paths to (2,2) = paths from above + paths from left

Result:

Final DP grid:
[1, 1, 1]
[1, 2, 3]
[1, 3, 6]
Total unique paths = 6

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

int uniquePaths(int m, int n) {
    int** dp = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        dp[i] = (int*)malloc(n * sizeof(int));
    }

    // Initialize first row with 1s
    for (int col = 0; col < n; col++) {
        dp[0][col] = 1;
    }

    // Initialize first column with 1s
    for (int row = 0; row < m; row++) {
        dp[row][0] = 1;
    }

    // Fill the dp table
    for (int row = 1; row < m; row++) {
        for (int col = 1; col < n; col++) {
            dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
        }
    }

    int result = dp[m - 1][n - 1];

    // Free memory
    for (int i = 0; i < m; i++) {
        free(dp[i]);
    }
    free(dp);

    return result;
}

int main() {
    int m = 3, n = 3;
    int paths = uniquePaths(m, n);
    printf("Total unique paths in a %dx%d grid: %d\n", m, n, paths);
    return 0;
}

for (int col = 0; col < n; col++) { dp[0][col] = 1; }

Initialize first row with 1s -- only one way to move right

for (int row = 0; row < m; row++) { dp[row][0] = 1; }

Initialize first column with 1s -- only one way to move down

dp[row][col] = dp[row - 1][col] + dp[row][col - 1];

Calculate paths for current cell by adding paths from top and left

Output

Total unique paths in a 3x3 grid: 6

Complexity Analysis

Time: O(m*n) because we fill each cell in the grid once

Space: O(m*n) because we store path counts for each cell in a 2D array

vs Alternative: Compared to recursive approach without memoization which is exponential, DP is much faster and uses extra space to store results

Edge Cases

1x1 grid

Only one cell means only one path (start is end)

DSA C

for (int col = 0; col < n; col++) { dp[0][col] = 1; }

1 row grid (1xN)

Only one path moving right along the row

DSA C

for (int col = 0; col < n; col++) { dp[0][col] = 1; }

1 column grid (Mx1)

Only one path moving down along the column

DSA C

for (int row = 0; row < m; row++) { dp[row][0] = 1; }

When to Use This Pattern

When a problem asks for counting ways to reach a point in a grid with restricted moves, use grid DP to build solutions from smaller subproblems.

Common Mistakes

Mistake: Not initializing first row and first column with 1s
Fix: Explicitly set dp[0][col] and dp[row][0] to 1 before filling the rest

Mistake: Adding dp[row][col - 1] and dp[row - 1][col] in wrong order or indices
Fix: Always add dp from top cell and left cell correctly: dp[row - 1][col] + dp[row][col - 1]

Summary

Calculates the number of unique paths from top-left to bottom-right in a grid moving only right or down.

Use when you need to count possible routes in a grid with movement restrictions.

The key insight is that paths to a cell equal sum of paths to the cell above and to the left.

Practice

1. What does the problem "Unique Paths in Grid DP" ask you to find?

easy

A. The maximum sum path from the top-left to the bottom-right corner of a grid.

B. The shortest path length from the top-left to the bottom-right corner of a grid.

C. The number of obstacles in the grid.

D. The number of different ways to move from the top-left to the bottom-right corner of a grid using only right and down moves.

Solution

1. Step 1: Understand the problem goal

   The problem asks for counting all possible paths from the start (top-left) to the end (bottom-right) moving only right or down.

2. Step 2: Clarify movement constraints

   Only moves allowed are right or down, no diagonal or backward moves.

3. Final Answer:

   The number of different ways to move from the top-left to the bottom-right corner of a grid using only right and down moves. -> Option D

4. Quick Check:

   Unique paths = count of right/down moves combinations [OK]

Hint: Count paths by moving only right or down [OK]

Common Mistakes:

• Thinking diagonal moves are allowed
• Confusing path count with shortest path
• Counting obstacles instead of paths

2. Which of the following is the correct way to initialize the DP array for a grid of size m x n in C?

easy

A. int dp[m][n] = {0};

B. int dp[m][n]; dp = 0;

C. int dp[m][n]; memset(dp, 0, sizeof(dp));

D. int dp[m][n] = NULL;

Solution

1. Step 1: Understand array initialization in C

   Arrays cannot be assigned directly after declaration; memset is used to set all bytes to zero.

2. Step 2: Check each option

   int dp[m][n] = {0}; tries to initialize with {0} which works only for static arrays, not variable length arrays. int dp[m][n]; memset(dp, 0, sizeof(dp)); uses memset correctly. int dp[m][n]; dp = 0; tries invalid assignment. int dp[m][n] = NULL; assigns NULL which is invalid for arrays.

3. Final Answer:

   int dp[m][n]; memset(dp, 0, sizeof(dp)); -> Option C

4. Quick Check:

   Use memset to zero initialize arrays in C [OK]

Hint: Use memset to zero initialize arrays in C [OK]

Common Mistakes:

• Trying to assign 0 directly to array
• Using NULL for arrays
• Assuming {0} works for variable length arrays

3. What is the output of the following code snippet for m=3, n=3?

int uniquePaths(int m, int n) {
    int dp[m][n];
    memset(dp, 0, sizeof(dp));
    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];
}
printf("%d", uniquePaths(3, 3));

medium

A. 3

B. 6

C. 9

D. 1

Solution

1. Step 1: Initialize first row and column

   First row and column are set to 1 because only one way to reach cells in first row (all right moves) or first column (all down moves).

2. Step 2: Fill dp table using sum of top and left cells

   For each cell dp[i][j], value = dp[i-1][j] + dp[i][j-1]. For 3x3 grid, dp[2][2] = 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Unique paths in 3x3 grid = 6 [OK]

Hint: Sum paths from top and left cells to fill DP [OK]

Common Mistakes:

• Not initializing first row and column to 1
• Adding instead of summing dp[i-1][j] and dp[i][j-1]
• Returning wrong dp cell

4. Find the error in this code snippet for unique paths calculation:

int uniquePaths(int m, int n) {
    int dp[m][n];
    memset(dp, 0, sizeof(dp));
    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];
}

medium

A. The loops initializing dp go out of bounds causing runtime error.

B. The dp array is not zero initialized.

C. The return statement returns wrong cell.

D. The nested loops start from 0 instead of 1.

Solution

1. Step 1: Check loop bounds for initialization

   Loops use <= m and <= n which causes index to go out of bounds since valid indices are 0 to m-1 and 0 to n-1.

2. Step 2: Identify correct loop bounds

   Loops should use < m and < n to avoid accessing invalid indices.

3. Final Answer:

   The loops initializing dp go out of bounds causing runtime error. -> Option A

4. Quick Check:

   Array indices must be within 0 to size-1 [OK]

Hint: Use < not <= for array indices in loops [OK]

Common Mistakes:

• Using <= instead of < in loops
• Ignoring array bounds causing crashes
• Incorrect initialization of dp array

5. Given a 4x4 grid with some blocked cells (obstacles) represented by 1, how would you modify the unique paths DP solution to count paths avoiding obstacles? Grid:

0 0 0 0
0 1 0 0
0 0 1 0
0 0 0 0

hard

A. Set dp[i][j] = 0 if cell is blocked; else dp[i][j] = dp[i-1][j] + dp[i][j-1].

B. Ignore obstacles and calculate paths normally.

C. Set dp[i][j] = 1 for blocked cells and 0 otherwise.

D. Only count paths that move diagonally to avoid obstacles.

Solution

1. Step 1: Mark blocked cells in dp as zero

   If a cell is blocked (value 1), no paths can go through it, so dp[i][j] = 0.

2. Step 2: Calculate dp for free cells

   For free cells (value 0), dp[i][j] = dp[i-1][j] + dp[i][j-1], summing paths from top and left.

3. Final Answer:

   Set dp[i][j] = 0 if cell is blocked; else dp[i][j] = dp[i-1][j] + dp[i][j-1]. -> Option A

4. Quick Check:

   Blocked cells have zero paths [OK]

Hint: Zero dp for obstacles, sum paths for free cells [OK]

Common Mistakes:

• Ignoring obstacles in path count
• Assigning 1 to blocked cells
• Using diagonal moves to avoid obstacles