[Dynamic Programming] Minimum Path Sum in a Grid - Medium

The Minimum Path Sum in a Grid is a problem. We need to find the path from the top-left corner to the bottom-right corner of a grid. Each cell has a non-negative number. Our goal is to get the smallest sum of the numbers along the path. We can only move down or to the right. We often solve this problem using dynamic programming. This method builds solutions step by step by keeping track of the results we find.

In this article, we will look closely at the Minimum Path Sum in a Grid problem. First, we will give a short overview of the solution and explain the problem statement. After that, we will talk about the dynamic programming approach. We will show you how to do this in Java, Python, and C++. We will also talk about iterative methods, how to make space use better, common mistakes we can make, and answer some questions people often ask about this problem.

  • [Dynamic Programming] Minimum Path Sum in a Grid - Medium Solution Overview
  • Understanding the Problem Statement for Minimum Path Sum
  • Dynamic Programming Approach for Minimum Path Sum in a Grid
  • Java Implementation of Minimum Path Sum in a Grid
  • Python Implementation of Minimum Path Sum in a Grid
  • C++ Implementation of Minimum Path Sum in a Grid
  • Iterative Approach for Minimum Path Sum in a Grid
  • Optimizing Space Complexity in Minimum Path Sum Solution
  • Common Mistakes to Avoid in Minimum Path Sum Problem
  • Frequently Asked Questions

Understanding the Problem Statement for Minimum Path Sum

The Minimum Path Sum problem is about finding a way from the top-left corner to the bottom-right corner of a grid. Each cell has a value that is a non-negative number. Our goal is to make the sum of the values along the path as small as possible. We can only move down or to the right.

Problem Definition

  • Input: A 2D grid grid with size m x n. Each cell grid[i][j] shows the cost of entering that cell.
  • Output: The minimum path sum from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1).

Example

Look at this grid:

[
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]

The minimum path sum is 7. We get this by taking the path 1 → 3 → 1 → 1. This gives us the sum 1 + 3 + 1 + 1 = 6.

Constraints

  • The grid must be at least 1x1.
  • All values in the grid are non-negative integers.

We need to understand the problem well to find a good solution using dynamic programming. We break the problem into smaller parts. Then, we store results we find along the way. Finally, we build the solution step by step.

Dynamic Programming Approach for Minimum Path Sum in a Grid

The Minimum Path Sum problem in a grid is about finding the smallest sum of a path from the top-left corner to the bottom-right corner. We can only move down or right. We can solve this problem well with a dynamic programming method.

Dynamic Programming Table

  1. State Definition: We can say dp[i][j] is the minimum path sum to reach cell (i, j).

  2. Recurrence Relation:

    • For the first cell:

      dp[0][0] = grid[0][0]

    • For the first row and first column:

      dp[i][0] = dp[i-1][0] + grid[i][0]  (for all i)
dp[0][j] = dp[0][j-1] + grid[0][j]  (for all j)

    • For other cells:

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

  3. Base Case: We start with dp[0][0] set to the value in the top-left corner of the grid.

  4. Result: We find the answer in dp[m-1][n-1], where m and n are the grid sizes.

Example

For a grid like this:

1 3 1
1 5 1
4 2 1

The dp table will look like this:

1  4  5
2  7  6
6  8  7

The minimum path sum is 7.

Time and Space Complexity

  • Time Complexity: (O(m n))
  • Space Complexity: (O(m n)) for the dp table.

Implementation Example

Here is a Java code for the dynamic programming solution to the Minimum Path Sum problem:

public class MinimumPathSum {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
}

We can also make this approach better for space by using just two arrays instead of a full dp table. The main point is that dynamic programming helps us break the problem down into smaller parts. This leads to a good solution for the Minimum Path Sum in a grid. For more on dynamic programming, check articles like Dynamic Programming - Unique Paths in a Grid.

Java Implementation of Minimum Path Sum in a Grid

To solve the Minimum Path Sum problem in a grid with Java, we can use dynamic programming. We will go through the grid and update each cell. Each cell will show the minimum path sum from the top-left corner to that cell.

Here is a simple implementation:

public class MinimumPathSum {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;

        // Update the first row
        for (int i = 1; i < n; i++) {
            grid[0][i] += grid[0][i - 1];
        }

        // Update the first column
        for (int j = 1; j < m; j++) {
            grid[j][0] += grid[j - 1][0];
        }

        // Update the rest of the grid
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }

        return grid[m - 1][n - 1];
    }

    public static void main(String[] args) {
        MinimumPathSum solution = new MinimumPathSum();
        int[][] grid = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };
        System.out.println("Minimum Path Sum: " + solution.minPathSum(grid)); // Output: 7
    }
}

Explanation of the Code

  • Input Check: The function starts by checking if the grid is empty.
  • Grid Size: We find out the number of rows (m) and columns (n).
  • First Row Setup: We fill the first row by adding sums from the left side.
  • First Column Setup: We fill the first column by adding sums from above.
  • Dynamic Programming Update: For each cell, we add its value to the minimum of the two cells we can come from (above or left).
  • Final Result: The bottom-right cell of the grid gives the minimum path sum.

This Java implementation helps to find the minimum path sum in a grid using dynamic programming ideas. For more reading, you can check out similar problems like Minimum Path Sum in a Grid with No Obstacles.

Python Implementation of Minimum Path Sum in a Grid

To solve the Minimum Path Sum problem in a grid with Python, we use a simple dynamic programming method. We create a 2D array called dp. Each dp[i][j] shows the minimum path sum to reach the cell (i, j) from the starting cell (0, 0).

Here is the step-by-step way to do it:

  1. Initialize the DP array: First, we make a 2D list dp that has the same size as the input grid. The value dp[i][j] will be the minimum path sum to get to that cell.

  2. Base case: Set the starting point dp[0][0] equal to grid[0][0].

  3. Fill the first row and column: We can only reach any cell in the first row from the left. For the first column, we can only come from above.

  4. Fill the rest of the DP array: For each cell (i, j), we can find the minimum path sum like this:

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

  5. Result: The value at dp[m-1][n-1] (where m is the number of rows and n is the number of columns) will tell us the minimum path sum to the bottom-right corner of the grid.

Here is the Python code for this method:

def minPathSum(grid):
    if not grid:
        return 0
    
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    dp[0][0] = grid[0][0]
    
    # Fill the first row
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # Fill the first column
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    # Fill the rest of the dp array
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    return dp[m-1][n-1]

# Example usage
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(minPathSum(grid))  # Output: 7

In this code, the function minPathSum takes a 2D list called grid and gives back the minimum path sum from the top-left corner to the bottom-right corner. The example shows how to use the function with a sample grid.

For more examples about path sums in grids, you can check the article Dynamic Programming - Unique Paths in a Grid.

C++ Implementation of Minimum Path Sum in a Grid

To solve the Minimum Path Sum problem in a grid using C++, we can use a simple dynamic programming method. We will create a 2D DP array. Each cell in this array shows the minimum path sum to reach that cell from the top-left corner.

C++ Code Implementation

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();

    // Create a DP table
    vector<vector<int>> dp(m, vector<int>(n, 0));

    // Initialize the top-left corner
    dp[0][0] = grid[0][0];

    // Fill the first row
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }

    // Fill the first column
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }

    // Fill the rest of the dp table
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
        }
    }

    // The bottom-right corner contains the answer
    return dp[m-1][n-1];
}

int main() {
    vector<vector<int>> grid = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };
    
    cout << "Minimum Path Sum: " << minPathSum(grid) << endl;
    return 0;
}

Explanation

  • The minPathSum function takes a 2D vector called grid as input.
  • We create a DP table with the same size as the grid.
  • We start by setting the first cell with the value from the grid’s top-left corner.
  • We fill the first row and the first column based on the sums.
  • For the other cells, we calculate the DP value by adding the current grid cell with the smallest value from the cell above or the cell to the left.
  • Finally, the value in the bottom-right corner of the DP table gives us the minimum path sum.

This method runs in O(mn) time and uses O(mn) space. If you want to learn more about similar dynamic programming problems, we can check out the Dynamic Programming: Unique Paths in a Grid article.

Iterative Approach for Minimum Path Sum in a Grid

We can solve the Minimum Path Sum in a grid by using a simple method called bottom-up dynamic programming. This way, we fill the grid so that each cell shows the minimum path sum to reach that cell from the top-left corner. The main idea is to go through each cell and update its value based on the minimum sum from the cell above and the cell to the left.

Steps:

  1. Initialization: First, we look at the first row and first column. They can only be reached from one way.
  2. Iterate through the grid: For each cell in the grid starting from (1,1), we update its value. The new value is its own value plus the minimum of the value from the cell above it and the cell to its left.
  3. Result: The value in the bottom-right corner of the grid gives us the minimum path sum.

Pseudocode:

function minPathSum(grid):
    if grid is empty:
        return 0
    
    rows = grid.length
    cols = grid[0].length
    
    for i from 0 to rows - 1:
        for j from 0 to cols - 1:
            if i == 0 and j == 0:
                continue
            if i == 0:
                grid[i][j] += grid[i][j - 1]
            else if j == 0:
                grid[i][j] += grid[i - 1][j]
            else:
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])
    
    return grid[rows - 1][cols - 1]

Java Implementation:

public int minPathSum(int[][] grid) {
    if (grid.length == 0) return 0;
    
    int rows = grid.length;
    int cols = grid[0].length;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (i == 0 && j == 0) continue;
            if (i == 0) grid[i][j] += grid[i][j - 1];
            else if (j == 0) grid[i][j] += grid[i - 1][j];
            else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        }
    }
    return grid[rows - 1][cols - 1];
}

Python Implementation:

def minPathSum(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])

    for i in range(rows):
        for j in range(cols):
            if i == 0 and j == 0:
                continue
            if i == 0:
                grid[i][j] += grid[i][j - 1]
            elif j == 0:
                grid[i][j] += grid[i - 1][j]
            else:
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])

    return grid[rows - 1][cols - 1]

C++ Implementation:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty()) return 0;

        int rows = grid.size();
        int cols = grid[0].size();

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0) grid[i][j] += grid[i][j - 1];
                else if (j == 0) grid[i][j] += grid[i - 1][j];
                else grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[rows - 1][cols - 1];
    }
};

This iterative way helps us find the minimum path sum in O(m * n) time. We can also make it use less space, which we will explain next. For more on dynamic programming, please check out Dynamic Programming: Unique Paths in a Grid.

Optimizing Space Complexity in Minimum Path Sum Solution

In the Minimum Path Sum problem, we want to find the path from the top-left corner to the bottom-right corner of a grid. This path should have the smallest sum of values. The usual way to solve this uses a 2D array to keep track of results. But this can use a lot of space. We can optimize it and use less space.

Space Optimization

  1. In-Place Updates: We can update the original grid instead of using a separate 2D array. This means we store the minimum path sums directly in the grid. This change will reduce the extra space needed to O(1).

  2. Single Array Approach: We can use just one 1D array to store the minimum path sums for the current row. This works well because we only need the values from the previous row to find the current row’s values.

Java Implementation Example

public int minPathSum(int[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int m = grid.length, n = grid[0].length;
    
    // Use a single array to store the minimum path sums
    int[] dp = new int[n];
    
    // Initialize the first cell
    dp[0] = grid[0][0];
    
    // Fill the first row
    for (int j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    
    // Fill the rest of the grid
    for (int i = 1; i < m; i++) {
        dp[0] += grid[i][0]; // Update first column
        for (int j = 1; j < n; j++) {
            dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }
    
    return dp[n - 1]; // Bottom-right corner
}

Python Implementation Example

def minPathSum(grid):
    if not grid or not grid[0]:
        return 0
    
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    
    dp[0] = grid[0][0]
    
    for j in range(1, n):
        dp[j] = dp[j - 1] + grid[0][j]
    
    for i in range(1, m):
        dp[0] += grid[i][0]
        for j in range(1, n):
            dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
    
    return dp[n - 1]

C++ Implementation Example

int minPathSum(vector<vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n);
    
    dp[0] = grid[0][0];
    
    for (int j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    
    for (int i = 1; i < m; i++) {
        dp[0] += grid[i][0];
        for (int j = 1; j < n; j++) {
            dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }
    
    return dp[n - 1];
}

Key Points

  • We optimize the space complexity to O(n) instead of O(m*n).
  • The implementation updates the DP array in place. This really helps in using less memory.
  • This optimization is very important for big grids. It helps improve performance and reduce memory use.

For more reading on dynamic programming and similar topics, you can check articles like Dynamic Programming: Minimum Path Sum in a Grid with No Obstacles and Dynamic Programming: Unique Paths in a Grid.

Common Mistakes to Avoid in Minimum Path Sum Problem

When we solve the Minimum Path Sum problem with dynamic programming, we should be careful. Some common mistakes can make our solution wrong. Here are some important points to keep in mind:

  1. Incorrect Initialization:
    • If we do not start the DP table correctly, we can get wrong answers. Make sure the first cell, usually the top-left one, starts with the value from the grid.
    dp[0][0] = grid[0][0];
  2. Boundary Conditions:
    • We must handle special cases. For example, single-row or single-column grids can cause errors if we do not check the grid size first. Always check the grid’s size before using its values.
  3. Updating the DP Table:
    • If we overwrite values in the DP table without looking at previous results, we can get wrong path sums. Always update the current cell by using the smallest value from the cell above or the cell to the left.
    dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
  4. Ignoring Grid Values:
    • We should always include values from the grid cells in our calculations. The total path sum depends on the grid’s values, not just the path we take.
  5. Space Complexity Optimization:
    • We can save memory by using space-saving techniques. Instead of a two-dimensional array, we can use a one-dimensional array when we can.
    vector<int> dp(n, 0);
  6. Not Saving Intermediate Results:
    • If we do not save intermediate results in the DP table, we will calculate values again and again. This makes our solution slow. Always save results to avoid repeating calculations.
  7. Incorrect Result Extraction:
    • We need to get the final result from the right cell in the DP table. Usually, the minimum path sum is in the bottom-right cell after all calculations.
  8. Overlooking Obstacle Handling:
    • If the problem has obstacles, we must handle them correctly. Cells with obstacles should not add to the path sum and should be marked properly.
  9. Misunderstanding Grid Traversal:
    • We must know how to move (only down and right) and apply the logic correctly to go through the grid. If we make mistakes in this logic, we can check wrong paths.
  10. Not Testing Edge Cases:
  • We need to test edge cases like empty grids or grids with just one element. If we do not test these, we can see unexpected problems. Always include tests for these cases.

By avoiding these mistakes, we can implement the Minimum Path Sum solution well using dynamic programming. This will give us correct answers and good performance. For more reading on similar dynamic programming problems, we can check articles like Dynamic Programming: Unique Paths in a Grid and Dynamic Programming: Minimum Path Sum in a Grid with No Obstacles.

Frequently Asked Questions

1. What is the Minimum Path Sum problem in a grid?

The Minimum Path Sum problem is about finding the best path from the top-left corner to the bottom-right corner of a grid. This path should have the smallest sum of values along the way. We can only move down or to the right at any time. This problem is a good example of dynamic programming. It helps us understand how to work with grid-based algorithms.

2. How can dynamic programming be applied to solve Minimum Path Sum in a grid?

We can use dynamic programming to solve the Minimum Path Sum problem by breaking it into smaller parts. We store the minimum path sums at each cell in the grid. This way, we can build the final answer without doing the same work again. It makes our solution faster and easier to manage.

3. What is the time complexity of the Minimum Path Sum algorithm?

The time complexity of the Minimum Path Sum algorithm is O(m * n). Here m is the number of rows and n is the number of columns in the grid. We get this speed by filling a DP table using values we already calculated. This means we visit each cell only one time.

4. How can I optimize the space complexity in the Minimum Path Sum problem?

To make space usage better in the Minimum Path Sum problem, we can use one array instead of a two-dimensional array. By updating this single array as we go, we can lower the space complexity from O(m * n) to O(n). This way, we still keep the information we need to find the minimum path sum.

5. Are there common mistakes to avoid when solving the Minimum Path Sum problem?

Some common mistakes when working on the Minimum Path Sum problem are not starting the DP array correctly, not checking the grid boundaries, and not understanding that we can only move down or right. We should carefully check edge cases and test with different grid sizes. For more practice, we can look at other dynamic programming problems like the Unique Paths in a Grid.