Minimum Path Sum in Grid in DSA C - Build from Scratch

Minimum Path Sum in Grid

📖 Scenario: Imagine you are helping a delivery robot find the easiest path through a city grid. Each block has a cost representing how hard it is to cross. The robot can only move right or down. Your job is to find the path with the smallest total cost from the top-left corner to the bottom-right corner.

🎯 Goal: Build a program that calculates the minimum path sum in a grid of costs, moving only right or down.

📋 What You'll Learn

Create a 2D array called grid with exact values

Create two integer variables rows and cols for grid size

Use nested for loops to compute minimum path sums

Print the minimum path sum value

💡 Why This Matters

🌍 Real World

Finding the easiest or cheapest path in a grid is useful in robotics, GPS navigation, and game development.

💼 Career

Understanding grid-based dynamic programming helps in software roles involving pathfinding, optimization, and algorithm design.

1

Create the grid data

Create a 2D integer array called grid with 3 rows and 3 columns containing these exact values: {{1,3,1},{1,5,1},{4,2,1}}. Also create integer variables rows and cols with values 3 and 3 respectively.

DSA C

int grid[3][3] = {{1,3,1},{1,5,1},{4,2,1}};
int rows = 3;
int cols = 3;
// Your code here

Hint

Use curly braces to set the 2D array values exactly as shown.

2

Create a 2D array for minimum path sums

Create a 2D integer array called dp with the same size as grid (3 rows and 3 columns) to store minimum path sums.

DSA C

int grid[3][3] = {{1,3,1},{1,5,1},{4,2,1}};
int rows = 3;
int cols = 3;
int dp[3][3];
// Your code here

Hint

Declare dp with the same dimensions as grid.

3

Calculate minimum path sums using nested loops

Use nested for loops with variables i and j to fill dp with minimum path sums. Initialize dp[0][0] with grid[0][0]. For the first row, set dp[0][j] as dp[0][j-1] + grid[0][j]. For the first column, set dp[i][0] as dp[i-1][0] + grid[i][0]. For other cells, set dp[i][j] as grid[i][j] plus the minimum of dp[i-1][j] and dp[i][j-1].

DSA C

int grid[3][3] = {{1,3,1},{1,5,1},{4,2,1}};
int rows = 3;
int cols = 3;
int dp[3][3];
// Your code here

Hint

Fill the first row and column first, then fill the rest using the minimum of top and left neighbors.

4

Print the minimum path sum

Print the value of dp[rows-1][cols-1] using printf to display the minimum path sum.

DSA C

int grid[3][3] = {{1,3,1},{1,5,1},{4,2,1}};
int rows = 3;
int cols = 3;
int dp[3][3];
dp[0][0] = grid[0][0];
for (int j = 1; j < cols; j++) {
    dp[0][j] = dp[0][j-1] + grid[0][j];
}
for (int i = 1; i < rows; i++) {
    dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int i = 1; i < rows; i++) {
    for (int j = 1; j < cols; j++) {
        dp[i][j] = grid[i][j] + (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]);
    }
}
// Your code here

Hint

Use printf("%d\n", dp[rows-1][cols-1]); to print the result.

Practice

1. What does the "Minimum Path Sum in Grid" problem ask you to find?
Given a grid of numbers, find the path from top-left to bottom-right with the smallest sum. Which is true?

easy

A. Find the path with the smallest sum moving only right or down.

B. Find the path with the largest sum moving in any direction.

C. Find the path with the smallest sum moving diagonally only.

D. Find the path with the smallest sum moving left or up.

Solution

1. Step 1: Understand the movement constraints

   The problem allows moving only right or down from each cell in the grid.

2. Step 2: Identify the goal

   The goal is to find the path from the top-left corner to the bottom-right corner with the minimum sum of all numbers on the path.

3. Final Answer:

   Find the path with the smallest sum moving only right or down. -> Option A

4. Quick Check:

   Minimum path sum = smallest sum with right/down moves [OK]

Hint: Remember: only right or down moves allowed [OK]

Common Mistakes:

• Thinking diagonal moves are allowed
• Looking for maximum sum instead of minimum
• Moving left or up which is not allowed

2. Which of the following C code snippets correctly initializes a 2D array named grid with 3 rows and 3 columns filled with zeros?

easy

A. int grid[3][3] = {1};

B. int grid[3][3] = {{1}};

C. int grid[3][3]; memset(grid, 0, sizeof(grid));

D. int grid[3][3] = { {0,0,0}, {0,0,0}, {1,1,1} };

Solution

1. Step 1: Understand array initialization in C

   Initializing a 2D array with zeros can be done by setting all elements to zero using memset after declaration.

2. Step 2: Check each option

   int grid[3][3]; memset(grid, 0, sizeof(grid)); declares the array and then uses memset to set all bytes to zero, correctly initializing all elements to zero.

3. Final Answer:

   int grid[3][3]; memset(grid, 0, sizeof(grid)); -> Option C

4. Quick Check:

   memset sets all elements to zero [OK]

Hint: Use memset for zeroing arrays in C [OK]

Common Mistakes:

• Using {1} only initializes first element
• Confusing single braces with double braces
• Not including string.h for memset

3. What is the output of the following C code that calculates the minimum path sum in a 2x2 grid?

int grid[2][2] = {{1, 3}, {1, 5}};
int dp[2][2];
dp[0][0] = grid[0][0];
for(int i=1; i<2; i++) dp[0][i] = dp[0][i-1] + grid[0][i];
for(int i=1; i<2; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for(int i=1; i<2; i++) {
  for(int j=1; j<2; j++) {
    dp[i][j] = (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]) + grid[i][j];
  }
}
printf("%d\n", dp[1][1]);

medium

A. 10

B. 8

C. 9

D. 7

Solution

1. Step 1: Calculate first row and column sums

   dp[0][0] = 1
   dp[0][1] = 1 + 3 = 4
   dp[1][0] = 1 + 1 = 2

2. Step 2: Calculate dp[1][1]

   Minimum of dp[0][1] = 4 and dp[1][0] = 2 is 2
   dp[1][1] = 2 + 5 = 7

3. Final Answer:

   7 -> Option D

4. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Fill dp row and column first, then inner cells [OK]

Common Mistakes:

• Adding max instead of min
• Incorrect dp initialization
• Off-by-one errors in loops

4. The following code attempts to compute the minimum path sum in a 3x3 grid but has a bug. What is the bug?

int grid[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
int dp[3][3];
dp[0][0] = grid[0][0];
for(int i=1; i<3; i++) dp[0][i] = dp[0][i-1] + grid[0][i];
for(int i=1; i<3; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for(int i=1; i<3; i++) {
  for(int j=1; j<3; j++) {
    dp[i][j] = dp[i-1][j] + dp[i][j-1] + grid[i][j];
  }
}

medium

A. The dp update adds both dp[i-1][j] and dp[i][j-1] instead of taking the minimum.

B. The loops start from 1 instead of 0.

C. The dp array is not initialized to zero.

D. The grid values are not accessed correctly.

Solution

1. Step 1: Analyze dp update formula

   The code adds dp[i-1][j] and dp[i][j-1] together plus grid[i][j], which is incorrect.

2. Step 2: Correct dp update

   It should take the minimum of dp[i-1][j] and dp[i][j-1], then add grid[i][j].

3. Final Answer:

   The dp update adds both dp[i-1][j] and dp[i][j-1] instead of taking the minimum. -> Option A

4. Quick Check:

   Use min(dp[i-1][j], dp[i][j-1]) + grid[i][j] [OK]

Hint: Use min, not sum, of top and left dp cells [OK]

Common Mistakes:

• Adding dp values instead of min
• Wrong loop ranges
• Not initializing dp[0][0]

5. Given a 3x3 grid:

int grid[3][3] = {
  {1, 3, 1},
  {1, 5, 1},
  {4, 2, 1}
};

Write the minimum path sum from top-left to bottom-right moving only right or down. What is the minimum sum?

hard

A. 8

B. 7

C. 9

D. 10

Solution

1. Step 1: Calculate dp first row and column

   dp[0][0] = 1
   dp[0][1] = 1+3=4
   dp[0][2] = 4+1=5
   dp[1][0] = 1+1=2
   dp[2][0] = 2+4=6

2. Step 2: Calculate inner dp cells

   dp[1][1] = min(dp[0][1], dp[1][0]) + 5 = min(4,2)+5=7
   dp[1][2] = min(dp[0][2], dp[1][1]) + 1 = min(5,7)+1=6
   dp[2][1] = min(dp[1][1], dp[2][0]) + 2 = min(7,6)+2=8
   dp[2][2] = min(dp[1][2], dp[2][1]) + 1 = min(6,8)+1=7

3. Final Answer:

   7 -> Option B

4. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Fill dp row-wise and column-wise, then inner cells [OK]

Common Mistakes:

• Choosing wrong min between top and left
• Incorrect dp initialization
• Misreading grid values