Why Unique Paths in Grid DP in DSA C?

The Big Idea

What if you could instantly know all possible ways to reach your goal without getting lost in endless counting?

The Scenario

Imagine you are in a city with a grid of streets. You want to walk from the top-left corner to the bottom-right corner, but you can only move right or down. Counting all possible routes by hand is like trying to list every path on a huge map.

The Problem

Manually counting paths is slow and confusing. As the grid grows, the number of paths grows very fast, making it easy to lose track or make mistakes. It's like trying to count every grain of sand on a beach.

The Solution

Dynamic Programming breaks the problem into smaller parts. It remembers the number of ways to reach each cell, so you don't repeat counting. This makes finding the total paths fast and easy, even for big grids.

Before vs After

✗ Before

int countPaths(int row, int col) {
    if (row == 0 || col == 0) return 1;
    return countPaths(row - 1, col) + countPaths(row, col - 1);
}

✓ After

int uniquePaths(int rows, int cols) {
    int dp[rows][cols];
    for (int i = 0; i < rows; i++) dp[i][0] = 1;
    for (int j = 0; j < cols; j++) dp[0][j] = 1;
    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[rows-1][cols-1];
}

What It Enables

This lets you quickly find how many ways to reach a destination in a grid, unlocking solutions to many path and movement problems.

Real Life Example

Robots in a warehouse need to find all possible routes to deliver items without backtracking. Using this method helps plan efficient paths.

Key Takeaways

Manual counting is slow and error-prone for large grids.

Dynamic Programming stores intermediate results to avoid repeated work.

This method efficiently calculates total unique paths in a grid.