LeetCode Minimum Path Sum Explained: A Dynamic Programming Approach

Introduction

The "Minimum Path Sum" problem is a classic dynamic programming challenge commonly found on platforms like LeetCode.

In this blog post, we will walk through the solution to the "Minimum Path Sum" problem step by step, using a dynamic programming approach. We’ll explain how the algorithm works and how it can be implemented in PHP.

Intuition Behind the Solution

To approach the "Minimum Path Sum" problem, we need to think about how to break down the pathfinding process into smaller, manageable subproblems.

The key insight comes from observing that the optimal path from the top-left corner to the bottom-right corner is built step by step, and each step depends on the previous decisions.

Here's the intuition

Subproblem Structure

At any point in the grid, the path to reach a cell depends on the minimum path sum of the cells that can be reached from it. Since we are only allowed to move right or down, each cell can either be reached from the cell directly above it or the cell directly to its left. This creates an optimal substructure where the best path to a cell can be derived from the best paths to its neighboring cells.

Bottom-Up Calculation

A natural approach is to solve the problem starting from the bottom-right corner (where the destination is) and working our way to the top-left corner (where the start is). This bottom-up approach ensures that when we're trying to compute the path sum for a given cell, the minimum path sums for the cells that could lead to it (right and down neighbors) are already calculated.

Code Explanation

Let's dive into the code to see how the solution works

function minPathSum($grid) {
    $row = count($grid);   // Get the number of rows in the grid
    $col = count($grid[0]); // Get the number of columns in the grid

    // Initialize the DP array with infinity values
    $dp = array_fill(0, $row, array_fill(0, $col, INF));

    // Start from the bottom-right corner of the grid
    $dp[$row][$col - 1] = 0;  // Set the destination point (bottom-right) as 0

    // Iterate through the grid from bottom-right to top-left
    for ($i = $row - 1; $i >= 0; $i--) {
        for ($j = $col - 1; $j >= 0; $j--) {

            // Get the minimum values for the possible moves (right or down)
            $right = $dp[$i][$j + 1] ?? PHP_INT_MAX; // Right cell value
            $down =  $dp[$i + 1][$j] ?? PHP_INT_MAX; // Down cell value

            // Calculate the minimum path sum for the current cell
            $dp[$i][$j] = $grid[$i][$j] + min($right, $down);
        }
    }

    // Return the minimum path sum from the top-left corner
    return $dp[0][0];
}

Step-by-Step Breakdown

• Grid Dimensions: The first step is determining the number of rows ($row) and columns ($col) in the grid. This helps us later to iterate through the grid properly.

• Initialize DP Table: We initialize a 2D dynamic programming array ($dp) with the same dimensions as the grid. Every cell is initially filled with infinity (INF), indicating that we haven't computed the minimum path sum yet. We set the destination cell ($dp[$row][$col-1]) to 0 because that's where we ultimately want to reach.

• Iterate Over the Grid: We process the grid from bottom-right to top-left since the solution for each cell depends on the values of its neighboring cells (either to the right or below). This ensures that when we're updating the current cell, the minimum values for its right and down neighbors are already computed.

• Dynamic Programming Transition: For each cell ($dp[$i][$j]), we calculate the minimum path sum by considering two possible directions:

  • The value of the cell to the right ($dp[$i][$j+1])

  • The value of the cell below ($dp[$i+1][$j])

The minimum of these two values is added to the current cell’s value in the grid ($grid[$i][$j]), giving us the smallest path sum for that particular cell.

• Return Result: Finally, once all cells are processed, we return the value in the top-left cell ($dp[0][0]), which contains the minimum path sum to reach the bottom-right corner.

Time Complexity

The time complexity of this solution is O(m * n), where m is the number of rows and n is the number of columns. This is because we visit each cell of the grid exactly once.

Conclusion

If you found this explanation helpful, please consider liking this post and sharing it with others. Your support motivates me to keep creating more valuable content. Stay tuned for more insights and solutions to coding challenges!