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.