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.