Unique Paths in Grid DP in DSA C - Deep Dive

Overview - Unique Paths in Grid DP

What is it?

Unique Paths in Grid DP is a way to count how many different ways you can move from the top-left corner to the bottom-right corner of a grid by only moving right or down. It uses a method called dynamic programming to break the problem into smaller parts and build the answer step-by-step. This helps solve the problem efficiently without repeating work. The grid is like a map, and each cell shows how many ways you can reach it.

Why it matters

Without this method, counting all possible paths would take too long because the number of paths grows very fast as the grid gets bigger. This problem shows how breaking a big problem into smaller parts saves time and effort. It helps in real-life tasks like robot navigation, game moves, or planning routes where you want to know all possible ways to reach a destination.

Where it fits

Before learning this, you should understand basic loops, arrays, and simple recursion. After this, you can learn more complex dynamic programming problems like those with obstacles, or problems that involve minimizing or maximizing costs along paths.

Mental Model

Core Idea

Count the ways to reach each cell by adding the ways to reach the cell above and the cell to the left.

Think of it like...

Imagine walking through a city grid where you can only move east or south. To get to any intersection, you can come from the intersection above or the one to the left. The total ways to get there is the sum of ways to get to those two intersections.

Start (0,0)
  ↓       ->
(0,0) -> (0,1) -> (0,2) -> ... -> (0,n-1)
  ↓       ↓       ↓             ↓
(1,0) -> (1,1) -> (1,2) -> ... -> (1,n-1)
  ↓       ↓       ↓             ↓
...     ...     ...           ...
  ↓       ↓       ↓             ↓
(m-1,0)->(m-1,1)->(m-1,2)-> ... -> (m-1,n-1) End

Build-Up - 7 Steps

1

Foundation

Understanding the grid and moves

Concept: Introduce the grid layout and allowed moves (right and down).

Imagine a grid with m rows and n columns. You start at the top-left corner (0,0) and want to reach the bottom-right corner (m-1,n-1). You can only move one step right or one step down at a time. The question is: how many different paths can you take?

Result

You understand the problem setup and allowed moves.

Knowing the movement rules is essential because it limits the possible paths and makes counting manageable.

2

Foundation

Brute force counting paths

Concept: Count paths by exploring all possible moves recursively.

One way is to try every path: from each cell, move right or down until you reach the end. Count 1 for each successful path. This is simple but slow because it repeats many calculations.

Result

You see that the number of paths grows very fast and brute force is inefficient.

Understanding brute force helps appreciate why we need a better method like dynamic programming.

3

Intermediate

Dynamic programming table setup

Concept: Use a 2D array to store the number of ways to reach each cell.

Create a 2D array dp with the same size as the grid. dp[i][j] will hold the number of unique paths to reach cell (i,j). Initialize dp[0][0] = 1 because there is exactly one way to be at the start.

Result

You have a structure to store intermediate results and avoid repeated work.

Storing results for each cell lets us build the solution step-by-step without recalculating.

4

Intermediate

Filling the DP table with recurrence

🤔Before reading on: do you think dp[i][j] depends on dp[i-1][j], dp[i][j-1], or both? Commit to your answer.

Concept: Each cell's paths count is the sum of paths from the cell above and the cell to the left.

For each cell (i,j), dp[i][j] = dp[i-1][j] + dp[i][j-1]. This works because you can only come from above or left. For the first row and first column, only one direction is possible, so dp values are 1.

Result

The dp table fills up with correct path counts for every cell.

Knowing the recurrence relation is the key to building the solution efficiently.

5

Intermediate

Implementing DP in C code

Concept: Translate the DP logic into a working C program.

Use nested loops to fill dp. Initialize dp[0][0] = 1. For first row and column, set dp[i][0] = 1 and dp[0][j] = 1. Then fill the rest using dp[i][j] = dp[i-1][j] + dp[i][j-1]. Finally, dp[m-1][n-1] is the answer.

Result

A complete C program that outputs the number of unique paths.

Implementing the logic in code solidifies understanding and shows practical use.

6

Advanced

Optimizing space usage in DP

🤔Before reading on: do you think we need the whole 2D dp array or can we use less memory? Commit to your answer.

Concept: Since dp[i][j] depends only on the current row and previous row, we can use a 1D array to save space.

Use a 1D array dp of size n. Initialize all elements to 1 for the first row. For each next row, update dp[j] = dp[j] + dp[j-1]. This way dp[j] holds the number of ways to reach cell (i,j).

Result

Memory usage reduces from O(m*n) to O(n) without changing the answer.

Understanding dependencies lets us optimize memory, which is important for large grids.

7

Expert

Handling obstacles and variations

🤔Before reading on: do you think the same DP approach works if some cells are blocked? Commit to your answer.

Concept: Modify DP to skip blocked cells by setting their dp value to 0 and only summing paths from reachable neighbors.

If a cell is blocked, dp[i][j] = 0. Otherwise, dp[i][j] = dp[i-1][j] + dp[i][j-1] if those cells are not blocked. This changes the counting to only valid paths.

Result

You can count unique paths even with obstacles in the grid.

Adapting DP to constraints shows its flexibility and real-world applicability.

Under the Hood

Dynamic programming works by storing the number of ways to reach each cell in a table, so when calculating a cell's value, it reuses previously computed results instead of recalculating paths repeatedly. This avoids exponential time complexity of brute force and reduces it to polynomial time. The recurrence relation dp[i][j] = dp[i-1][j] + dp[i][j-1] reflects the problem's overlapping subproblems and optimal substructure properties.

Why designed this way?

This approach was designed to solve path counting efficiently by exploiting the grid's structure and movement constraints. Alternatives like brute force were too slow. The DP method balances simplicity and performance, making it easy to implement and understand while scaling well for large grids.

┌─────────────┐
│ Start (0,0) │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ dp[i][j] =  │
│ dp[i-1][j] +│
│ dp[i][j-1]  │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Reuse stored│
│ results to  │
│ avoid recom-│
│ putation    │
└─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think the number of unique paths depends on the order you move right or down? Commit to yes or no.

Common Belief: The order of moves does not matter, so different sequences with the same moves count as the same path.

Reality: Each unique sequence of moves right and down counts as a different path, so order does matter in counting unique paths.

Why it matters: Misunderstanding this leads to undercounting paths and wrong answers.

Quick: Do you think you can move diagonally in the unique paths problem? Commit to yes or no.

Common Belief: You can move diagonally as well as right and down.

Reality: Only moves to the right or down are allowed; diagonal moves are not counted.

Why it matters: Allowing diagonal moves changes the problem and the counting method, leading to incorrect results if misunderstood.

Quick: Do you think the DP table must be fully filled before getting the answer? Commit to yes or no.

Common Belief: You must fill the entire dp table before you can know the number of unique paths.

Reality: You only need to fill up to the bottom-right cell; partial filling or early stopping is possible in some variations.

Why it matters: Knowing this can optimize computations in some cases and helps understand DP flexibility.

Quick: Do you think the number of unique paths can be calculated without storing intermediate results? Commit to yes or no.

Common Belief: You can calculate the number of unique paths using recursion without storing intermediate results efficiently.

Reality: Without storing intermediate results, the calculation is exponential and inefficient; DP stores results to avoid repeated work.

Why it matters: Ignoring this leads to slow programs that can't handle large grids.

Expert Zone

1

The DP solution exploits the grid's monotonic movement constraints, which means no cycles or backward moves, simplifying the recurrence.

2

Using combinatorial formulas (like binomial coefficients) can compute unique paths directly, but DP is more flexible for variations like obstacles.

3

Space optimization from 2D to 1D DP arrays is possible because each dp[i][j] depends only on the current and previous row, a subtle but powerful insight.

When NOT to use

This DP approach is not suitable if moves are allowed in more directions (like diagonals) or if the grid has complex constraints that break the simple recurrence. In such cases, graph algorithms or backtracking with pruning might be better.

Production Patterns

In real systems, this pattern is used for robot path planning, game AI movement options, and network routing where counting or enumerating paths is needed. Often combined with obstacle handling and cost minimization for practical use.

Connections

Pascal's Triangle

The unique paths counts correspond to binomial coefficients found in Pascal's Triangle.

Recognizing this connection allows using combinatorial formulas to compute paths directly without DP.

Graph Theory

The grid can be seen as a directed acyclic graph where edges represent allowed moves.

Understanding the problem as counting paths in a DAG helps apply graph algorithms and generalizes the approach.

Project Management (Critical Path Method)

Counting unique paths is similar to finding possible sequences of tasks in project scheduling.

This shows how path counting concepts apply beyond programming, helping plan and analyze workflows.

Common Pitfalls

#1 Confusing the starting cell's path count initialization.

Wrong approach:

int dp[m][n] = {0};
dp[0][0] = 0; // wrong initialization
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

Correct approach:

int dp[m][n] = {0};
dp[0][0] = 1; // correct initialization
for (int i = 1; i < m; i++) dp[i][0] = 1;
for (int j = 1; j < n; j++) dp[0][j] = 1;

Root cause:

Starting cell must have 1 path because you are already there; setting it to 0 causes all counts to be zero.

#2 Accessing out-of-bound indices when filling dp.

Wrong approach:

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1]; // no boundary check
}
}

Correct approach:

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int up = (i > 0) ? dp[i-1][j] : 0;
int left = (j > 0) ? dp[i][j-1] : 0;
dp[i][j] = (i == 0 && j == 0) ? 1 : up + left;
}
}

Root cause:

Not handling edges causes invalid memory access and wrong results.

#3 Using recursion without memoization leading to slow performance.

Wrong approach:

int uniquePaths(int i, int j) {
if (i == 0 && j == 0) return 1;
if (i < 0 || j < 0) return 0;
return uniquePaths(i-1, j) + uniquePaths(i, j-1);
}

Correct approach:

Use a dp array to store results and avoid repeated calls:
int dp[m][n];
// fill dp iteratively as shown before

Root cause:

Recursion without storing results repeats calculations exponentially.

Key Takeaways

Unique Paths in Grid DP counts how many ways to reach the bottom-right cell by moving only right or down.

Dynamic programming stores intermediate results to avoid repeated calculations and speeds up the solution.

Each cell's path count is the sum of the counts from the cell above and the cell to the left.

Space can be optimized from a 2D table to a 1D array because of the problem's structure.

The method adapts easily to variations like obstacles by adjusting the DP rules.