[Dynamic Programming] Minimum Path Sum in a Grid (No Obstacles) - Easy

Minimum Path Sum in a Grid (No Obstacles)

Minimum Path Sum in a Grid is a well-known dynamic programming problem. The goal is to find the smallest path sum from the top-left corner to the bottom-right corner of a grid. Each cell in the grid has a non-negative number. We can only move right or down. By using dynamic programming, we can find the minimum path sum easily. We store results in a table. This way, we don’t do the same calculations again. It helps us to get the best performance.

In this article, we will look at different ways to solve the Minimum Path Sum problem with dynamic programming. We will start by explaining the problem. Then, we will see the dynamic programming method in Java, Python, and C++. We will also talk about how to make space usage better. We will show recursive methods with memoization and explain iterative methods. In the end, we will check the time complexity of the solutions. We will also answer some common questions about this topic.

• Dynamic Programming Minimum Path Sum in a Grid without Obstacles - Easy
• Understanding the Problem Statement for Minimum Path Sum
• Dynamic Programming Approach to Minimum Path Sum in Java
• Dynamic Programming Approach to Minimum Path Sum in Python
• Dynamic Programming Approach to Minimum Path Sum in C++
• Optimizing Space Complexity for Minimum Path Sum
• Recursive Approach with Memoization for Minimum Path Sum
• Iterative Approach for Minimum Path Sum
• Time Complexity Analysis of Minimum Path Sum Solutions
• Frequently Asked Questions

For more information on dynamic programming, you can check related articles like Dynamic Programming: Fibonacci Number (Easy) and Dynamic Programming: Unique Paths in a Grid (Easy).

Understanding the Problem Statement for Minimum Path Sum

We want to solve the Minimum Path Sum problem. This problem asks us to find a way to go from the top-left corner of a grid to the bottom-right corner. We need to do this while keeping the sum of the values along the way as low as possible. We can only move down or to the right.

Problem Definition

• We have a grid that is m x n and is filled with numbers that are not negative. Our goal is to return the smallest sum of a path from the top-left cell (0,0) to the bottom-right cell (m-1,n-1).
• For example, look at this grid:

1   3   1
1   5   1
4   2   1

• The smallest path sum from (0,0) to (2,2) is 1 → 3 → 1 → 1, which gives us a total of 6.

Constraints

• The grid only has non-negative integers.
• The size of the grid will be between 1 and 100 for both m and n.

Example

Consider this grid:

2   1   3
4   5   6
7   8   9

The smallest path sum is 2 → 1 → 5 → 6, which adds up to 14.

Input/Output

• Input: A grid shown as a 2D list of integers.
• Output: A number that shows the minimum path sum.

We can solve this problem well by using dynamic programming methods. We will talk more about this in the next sections.

Dynamic Programming Approach to Minimum Path Sum in Java

To solve the Minimum Path Sum problem with dynamic programming in Java, we will use a 2D array. This array will hold the minimum path sums for each cell. Our goal is to find the smallest sum of the path from the top-left corner to the bottom-right corner of the grid. We can only move down or right.

Java 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;
        
        // Create a DP array
        int[][] dp = new int[m][n];
        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 array
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

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

Explanation

• Initialization: We start by setting the top-left corner with the value from the grid at (0,0).
• First Row and Column: We fill the first row from the left and the first column from above.
• Filling DP Array: For each cell, we find the minimum path sum. This is the value of the cell plus the smaller sum from the cell above or the cell to the left.
• Result: The bottom-right cell dp[m-1][n-1] holds the minimum path sum.

This method has a time cost of O(m * n) and a space cost of O(m * n) because of the DP array. To make it better, we can look at ways to reduce space cost in other parts.

For more tips on dynamic programming problems with grid paths, we can check the Unique Paths in a Grid article.

Dynamic Programming Approach to Minimum Path Sum in Python

We can solve the Minimum Path Sum problem using dynamic programming in Python. First, we create a 2D list. This list will store the minimum path sums to reach each cell in the grid. We can only move right or down. We start from the top-left corner (0, 0) and go to the bottom-right corner (m-1, n-1).

Here is a simple implementation:

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

    m, n = len(grid), len(grid[0])
    
    # Initialize the first row
    for j in range(1, n):
        grid[0][j] += grid[0][j - 1]
    
    # Initialize the first column
    for i in range(1, m):
        grid[i][0] += grid[i - 1][0]
    
    # Fill the rest of the grid
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i - 1][j], grid[i][j - 1])

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

Explanation of the Code:

• Initialization: First, we check if the grid is empty. If it is not, we get the size of the grid (m x n).
• First Row and Column: We fill the first row and first column. There is only one way to reach these cells, from the left or from above.
• Dynamic Programming Table Filling: For every cell in the grid, we find the minimum path sum. We do this by adding the current cell’s value to the minimum path sum from the top or left cells.
• Return Value: At the end, we return the minimum path sum to reach the bottom-right corner of the grid.

This dynamic programming approach has a time complexity of O(m*n) and a space complexity of O(1). We can modify the grid in place. This makes it efficient for our problem.

For more information on dynamic programming techniques, we can check articles on Fibonacci Numbers and Unique Paths in a Grid.

Dynamic Programming Approach to Minimum Path Sum in C++

We can solve the Minimum Path Sum problem in a grid using dynamic programming in C++. The main goal is to find a path from the top-left corner to the bottom-right corner of the grid. We want to minimize the sum of the values along the path. We can only move right or down.

C++ Code Implementation

Here is a simple way to implement this using a dynamic programming approach:

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

using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    
    // Initialize the first cell
    for (int i = 1; i < m; i++) {
        grid[i][0] += grid[i-1][0];
    }
    for (int j = 1; j < n; j++) {
        grid[0][j] += grid[0][j-1];
    }

    // Fill the grid with minimum path sums
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
        }
    }

    return grid[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; // Output: 7
    return 0;
}

Explanation of the Code

• Initialization: First, we set up the first row and first column of the grid. We can only reach these cells from one direction.
• Dynamic Programming Table Update: We go through the grid starting from cell (1, 1). We update each cell by adding the minimum of the cell above or the cell to the left to the current cell value.
• Result: The minimum path sum is saved in the bottom-right corner of the grid.

This method runs in O(m * n) time. It uses O(1) space if we change the input grid. So, it is efficient for solving the Minimum Path Sum problem in C++.

For more information about dynamic programming, we can look at Dynamic Programming - Unique Paths in a Grid.

Optimizing Space Complexity for Minimum Path Sum

We can make space usage better for the Minimum Path Sum problem in a grid. Instead of using a 2D array, we will use just one array. This is good because we only need to keep the current and previous row values while calculating.

Space Optimization Technique

1. Use a 1D Array: We keep a 1D array that shows the minimum path sum for the current row. This is easier than using a 2D array.

2. Update in Place: As we go through the grid, we update the array. We make sure to calculate the current row based on the previous row’s values.

Code Implementation

Java

public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[] dp = new int[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] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }

    return dp[n - 1];
}

Python

def minPathSum(grid):
    if not grid:
        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[-1]

C++

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> dp(n, 0);
        
        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];
    }
};

Benefits of Space Optimization

• Reduced Space Complexity: We cut down the space complexity from O(m*n) to O(n). This is better for big grids.
• Improved Performance: This helps the algorithm to run faster using less memory. This is important in competitive programming or with large data.

This better way is very important when we work with big grids. It helps keep the solution quick and workable. For more info on dynamic programming, check this: Dynamic Programming: Unique Paths in a Grid.

Recursive Approach with Memoization for Minimum Path Sum

Finding the minimum path sum in a grid using a recursive approach means we break the problem into smaller parts. We can use memoization to keep track of the results we already calculated. This step helps us avoid doing the same calculations again.

Problem Definition

We have a grid filled with non-negative numbers. Our goal is to find a path from the top-left corner to the bottom-right corner. We can only move down or right. We want to make sure that the sum of the numbers along the path is as small as possible.

Recursive Function with Memoization

Now, we will see how to write the recursive approach with memoization in Java, Python, and C++.

Java Implementation

import java.util.HashMap;

public class MinimumPathSum {
    public int minPathSum(int[][] grid) {
        return minPathSumHelper(grid, 0, 0, new HashMap<>());
    }

    private int minPathSumHelper(int[][] grid, int row, int col, HashMap<String, Integer> memo) {
        if (row == grid.length - 1 && col == grid[0].length - 1) {
            return grid[row][col];
        }
        if (row >= grid.length || col >= grid[0].length) {
            return Integer.MAX_VALUE;
        }
        String key = row + "," + col;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        int right = minPathSumHelper(grid, row, col + 1, memo);
        int down = minPathSumHelper(grid, row + 1, col, memo);
        int result = grid[row][col] + Math.min(right, down);
        memo.put(key, result);
        return result;
    }
}

Python Implementation

class MinimumPathSum:
    def minPathSum(self, grid):
        memo = {}
        return self.minPathSumHelper(grid, 0, 0, memo)

    def minPathSumHelper(self, grid, row, col, memo):
        if row == len(grid) - 1 and col == len(grid[0]) - 1:
            return grid[row][col]
        if row >= len(grid) or col >= len(grid[0]):
            return float('inf')
        key = (row, col)
        if key in memo:
            return memo[key]
        right = self.minPathSumHelper(grid, row, col + 1, memo)
        down = self.minPathSumHelper(grid, row + 1, col, memo)
        result = grid[row][col] + min(right, down)
        memo[key] = result
        return result

C++ Implementation

#include <vector>
#include <unordered_map>
#include <string>

class MinimumPathSum {
public:
    int minPathSum(std::vector<std::vector<int>>& grid) {
        std::unordered_map<std::string, int> memo;
        return minPathSumHelper(grid, 0, 0, memo);
    }

private:
    int minPathSumHelper(std::vector<std::vector<int>>& grid, int row, int col, std::unordered_map<std::string, int>& memo) {
        if (row == grid.size() - 1 && col == grid[0].size() - 1) {
            return grid[row][col];
        }
        if (row >= grid.size() || col >= grid[0].size()) {
            return INT_MAX;
        }
        std::string key = std::to_string(row) + "," + std::to_string(col);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }
        int right = minPathSumHelper(grid, row, col + 1, memo);
        int down = minPathSumHelper(grid, row + 1, col, memo);
        int result = grid[row][col] + std::min(right, down);
        memo[key] = result;
        return result;
    }
};

Key Points

• The recursive approach checks all possible paths.
• Using memoization stops us from calculating the same result many times.
• With memoization, the complexity is O(m*n) for a grid sized m x n. Without memoization, it can take much longer.

If we want to learn more about dynamic programming methods, we can check Dynamic Programming - Unique Paths in a Grid.

Iterative Approach for Minimum Path Sum

We can find the minimum path sum in a grid by using dynamic programming. This means we build a solution step by step. We will make a 2D array called dp. In this array, dp[i][j] shows the minimum path sum to get to cell (i, j) starting from cell (0, 0).

Steps:

• First, we set the first cell dp[0][0] with the value from the grid at (0, 0).
• Next, we fill in the first row and the first column of the dp array. There is only one way to get to these cells. We can come from the left for the row or from above for the column.
• For the other cells, we calculate the minimum path sum. We take the smaller value from the cell above and the cell to the left. Then we add the current cell’s value from the grid.

Example Code in Python:

def minPathSum(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]

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

    # Fill the first row
    for j in range(1, cols):
        dp[0][j] = dp[0][j - 1] + grid[0][j]

    # Fill the first column
    for i in range(1, rows):
        dp[i][0] = dp[i - 1][0] + grid[i][0]

    # Fill the rest of the dp array
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

    return dp[rows - 1][cols - 1]

Example Code in Java:

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

        int rows = grid.length, cols = grid[0].length;
        int[][] dp = new int[rows][cols];

        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] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[rows - 1][cols - 1];
    }
}

Example Code in C++:

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

        int rows = grid.size(), cols = grid[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols, 0));

        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] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[rows - 1][cols - 1];
    }
};

This iterative way helps us find the minimum path sum quickly. The time it takes is (O(m n)) and the space we need is also (O(m n)). Here (m) is the number of rows and (n) is the number of columns in the grid. For more about dynamic programming, we can look at articles on Unique Paths in a Grid and Minimum Cost Climbing Stairs.

Time Complexity Analysis of Minimum Path Sum Solutions

The minimum path sum problem is about finding the cheapest way from the top-left corner to the bottom-right corner of a grid. This grid is filled with non-negative numbers. We can solve this problem in a few ways. These ways are dynamic programming, recursion with memoization, and iterative methods. Each way has its own time complexities.

Dynamic Programming Approach

In the dynamic programming method, we use a 2D array dp. Here, dp[i][j] shows the minimum path sum to reach cell (i, j). The time complexity for filling this dp table is O(m * n). Here, m is the number of rows and n is the number of columns in the grid.

Java Implementation:

public int minPathSum(int[][] grid) {
    int m = grid.length, 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] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

Recursive Approach with Memoization

In this method, we look at the paths using recursion. We also have a memoization table to save results of subproblems. The time complexity stays O(m * n) because memoization stops us from doing the same calculations again.

Python Implementation:

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    memo = {}
    
    def dfs(i, j):
        if i == m - 1 and j == n - 1:
            return grid[i][j]
        if (i, j) in memo:
            return memo[(i, j)]
        
        down = float('inf') if i + 1 == m else dfs(i + 1, j)
        right = float('inf') if j + 1 == n else dfs(i, j + 1)
        
        memo[(i, j)] = grid[i][j] + min(down, right)
        return memo[(i, j)]
    
    return dfs(0, 0)

Iterative Approach

We can make the iterative method better by using a single-dimensional array instead of a 2D array. This saves space. The time complexity is still O(m * n) but the space complexity can be lower to O(n).

C++ Implementation:

int minPathSum(vector<vector<int>>& grid) {
    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];
}

Summary of Time Complexities

• Dynamic Programming: O(m * n)
• Recursion with Memoization: O(m * n)
• Iterative (Optimized Space): O(m * n)

For more reading on dynamic programming concepts, you can check articles like Dynamic Programming on Unique Paths in a Grid and Dynamic Programming on the Fibonacci Number.

Frequently Asked Questions

What is the Minimum Path Sum problem in a grid without obstacles?

The Minimum Path Sum problem means we need to find the way from the top left to the bottom right corner of a grid. Each cell has a non-negative number. This number shows the cost to step on that cell. Our goal is to find the path that has the least total cost. This problem is a common topic in algorithm studies. We can solve it well using different methods like iterative and recursive ways.

How does dynamic programming help in solving the Minimum Path Sum problem?

Dynamic programming is a strong method for solving problems like the Minimum Path Sum. It makes the problem easier by breaking it into smaller parts. We store the results of these parts so we do not calculate them again. This method makes the time needed much less than using simple recursive methods. By using a 2D array to keep track of the lowest costs at each cell, we can find the solution faster.

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 efficiency by filling out a dynamic programming table that shows the minimum cost to reach each cell. We can make the space complexity even better to O(n) if we only keep the current and the previous rows, not the whole grid.

Can you explain the difference between the iterative and recursive approaches for Minimum Path Sum?

The iterative approach for the Minimum Path Sum problem fills out a dynamic programming table from the bottom up. Each cell only depends on values that we calculated before. On the other hand, the recursive approach uses function calls to check all options. We usually add memoization to save results we find. Both methods can give the right answer, but the iterative way is usually faster and uses less space.

Are there similar problems to the Minimum Path Sum in dynamic programming?

Yes, there are many problems that are similar to Minimum Path Sum in dynamic programming. For example, the Unique Paths problem needs us to find the number of different paths to reach the bottom-right corner. Other similar problems are Climbing Stairs and Min Cost Climbing Stairs. These problems also use dynamic programming methods.