Tags: JavaScript, Algorithms, Dynamic Programming, Matrices

Imagine you’re a robot, starting at the top-left corner of a grid filled with non-negative integers. Your mission, should you choose to accept it, is to find a path to the bottom-right corner that minimizes the total sum of the numbers you encounter along the way. The catch? You can only move to the right or down.

Let’s take an example grid:

+---+---+---+
| 1 | 3 | 1 |
|---|---|---|
| 1 | 5 | 1 |
|---|---|---|
| 4 | 2 | 1 |
+---+---+---+

The minimum path sum here is 7, achieved by the path 1 → 3 → 1 → 1 → 1.

Now, let’s think about this like a robot. For any given cell, there are only two ways to enter: from the cell above or from the cell to the left. Therefore, the minimum path sum to any cell is the value of that cell plus the minimum of the path sums to the cell above and to the left.

We can represent this mathematically as:

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

This is our state transition equation. The initial state is dp[0][0] = grid[0][0], and for any i<0 or j<0, dp[i][j] = 0.

Here’s how we can implement this in JavaScript:

var minPathSum = function(grid) {
    const dp = []
    
    for(let i = 0; i < grid.length; i++) {
        const row = grid[i]
        dp[i] = []
        for(let j = 0; j < row.length; j++) {
            if(i === 0 && j === 0) dp[i][j] = grid[i][j]
            else if(i === 0) dp[i][j] = grid[i][j] + dp[i][j-1]
            else if(j === 0) dp[i][j] = grid[i][j] + dp[i-1][j]
            else dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1])
        }
    }
    return dp[grid.length-1][grid[0].length-1]
}

The time complexity of this algorithm is $O(M\times N)$ due to the two nested loops, where M and N are the dimensions of the grid.

The space complexity is also $O(M\times N)$ because we need to store the minimum path sum for each cell in the dp array.

So there you have it, a robot’s guide to navigating grids efficiently!