Unique Paths in Grid DP in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unique Paths Calculation in 3x3 Grid

What is the output of the following C code that calculates the number of unique paths in a 3x3 grid moving only right or down?

DSA C

#include <stdio.h>

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

int main() {
    printf("%d\n", uniquePaths(3, 3));
    return 0;
}

A 9

B 3

C 6

D 12

💡 Hint

Think about how many ways you can move right and down to reach the bottom-right corner.

The number of unique paths in a 3x3 grid moving only right or down is 6. This is calculated by dynamic programming where each cell is the sum of paths from the top and left cells.

🧠 Conceptual

intermediate

Number of Unique Paths in a 2x4 Grid

How many unique paths exist in a 2 rows by 4 columns grid if you can only move right or down?

A 6

B 5

C 7

D 4

💡 Hint

Use the formula for combinations or think about the dp approach.

The number of unique paths in a 2x4 grid is 4. You need to move right 3 times and down 1 time in any order. The number of ways is C(4,1) = 4.

❓ Predict Output

advanced

Output of Unique Paths with Obstacle Grid

What is the output of this C code that calculates unique paths in a 3x3 grid with an obstacle at position (1,1)? Obstacle cells are marked with 1 and cannot be passed.

DSA C

#include <stdio.h>

int uniquePathsWithObstacles(int obstacleGrid[3][3]) {
    int dp[3][3];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            dp[i][j] = 0;
        }
    }
    dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
    for (int i = 1; i < 3; i++) {
        dp[i][0] = (obstacleGrid[i][0] == 0 && dp[i-1][0] == 1) ? 1 : 0;
    }
    for (int j = 1; j < 3; j++) {
        dp[0][j] = (obstacleGrid[0][j] == 0 && dp[0][j-1] == 1) ? 1 : 0;
    }
    for (int i = 1; i < 3; i++) {
        for (int j = 1; j < 3; j++) {
            if (obstacleGrid[i][j] == 0) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return dp[2][2];
}

int main() {
    int grid[3][3] = {
        {0, 0, 0},
        {0, 1, 0},
        {0, 0, 0}
    };
    printf("%d\n", uniquePathsWithObstacles(grid));
    return 0;
}

A 2

B 3

C 1

D 0

💡 Hint

The obstacle blocks some paths, reducing total unique paths.

With an obstacle at (1,1), the number of unique paths reduces to 2. The dp table counts paths avoiding the obstacle.

🔧 Debug

advanced

Identify the Error in Unique Paths DP Code

What error will this C code produce when calculating unique paths in a 3x3 grid?

DSA C

#include <stdio.h>

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

int main() {
    printf("%d\n", uniquePaths(3, 3));
    return 0;
}

A Segmentation fault due to out-of-bounds array access

B Compilation error due to missing return statement

C Output is 0

D No error, output is 6

💡 Hint

Check the loop conditions for array indexing.

The loops use <= which causes index to go out of bounds, leading to segmentation fault at runtime.

🚀 Application

expert

Calculate Unique Paths in a 5x5 Grid with Obstacles

Given the following 5x5 grid with obstacles (1 marks obstacle, 0 free cell), how many unique paths exist from top-left to bottom-right moving only right or down?

DSA C

int grid[5][5] = {
    {0, 0, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {1, 0, 1, 0, 0},
    {0, 0, 0, 1, 0}
};

A 10

B 5

C 8

D 7

💡 Hint

Use dynamic programming to accumulate paths avoiding obstacles.

By filling dp table considering obstacles, the total unique paths to bottom-right is 5.