loading...
Cover image for Finding the Minimum Path Sum in a Grid with Dynamic Programming

Finding the Minimum Path Sum in a Grid with Dynamic Programming

alisabaj profile image Alisa Bajramovic Updated on ・7 min read

Algorithm of the Day (33 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 31 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays

The algorithm of the day is a bit trickier than yesterday's:

given an m x n grid filled with non-negative numbers, find a path from the top left to the bottom right which minimizes the sum of all numbers along its path. You can only move either down or right at any point.

For example, if you were given the input
[
[1,3,1],
[1,5,1],
[4,2,1]
]

the output should be 7, because the path that would produce the minimum sum would go 1 > 3 > 1 > 1 > 1.

The two main ways to solve this problem are Depth First Search and Dynamic Programming. Today, I'll be solving it using dynamic programming. First, I'll give a brief overview of what dynamic programming is. Then, I'll go over the general approach to this problem, and using JavaScript, I will solve the algorithm. Finally, I'll use an example and go through the problem, explaining each step.

What is Dynamic Programming?

You've probably done dynamic programming in the past, even if you've never heard the term before. As defined by Geeks for Geeks:

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

One common example of dynamic programming is the Fibonacci Problem. While you could solve for the nth Fibonacci number using recursion, the time complexity on that approach would be O(n^2). With dynamic programming, the time complexity would be O(n)--far preferable.

The Problem: Approaching It and Coding The Solution

The first thing I'll do is initiate a few variables that represent the rows and columns of the inputted grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  //...
}

Now, I want to create a new array called pathChange. The purpose of pathChange is to store the minimum sum path at each point in the inputted grid. Rather than modify the input, I'll make a new empty array which is the same size as the inputted grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  //...
}

Right now, we have an inputted grid, and an empty array of size m x n. The next thing to do is to set the starting square. Because, as per the algorithm instructions, we're beginning in the top left corner ([0][0]), we can initiate that point in the pathChange array to equal the value in the input grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  pathChange[0][0] = grid[0][0];

  //...
}

Now we'll want to build the edges of the pathChange array. Because we know that we can only ever move down or right, these initiations are going to be pretty straightforward: in the first row, we can only move right, and in the first column, we can only move down. So, we can build two for loops--one for the first column, and one for the first row.

For the first column, we'll go down each space in the pathChange array, and set it equal to the element just above it in the pathChange array, plus that element in the grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  pathChange[0][0] = grid[0][0];

  for (let i = 1; i < m; i++) {
    pathChange[i][0] = pathChange[i - 1][0] + grid[i][0]; 
  }

  //...
}

Now, for the first row, we'll do a very similar thing: we'll move from left to right, and set each element in the pathChange array equal to the one just to its left, plus the element in that location in the grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  pathChange[0][0] = grid[0][0];

  for (let i = 1; i < m; i++) {
    pathChange[i][0] = pathChange[i - 1][0] + grid[i][0]; 
  }

  for (let i = 1; i < n; i++) {
    pathChange[0][i] = pathChange[0][i - 1] + grid[0][i];
  }

  //...
}

At this point, we have the top and left edges of the pathChange filled out with numbers representing the sum up to that point. All that's left to do is fill out the remainder of the pathChange array.

In order to find the minimum sum path of the remaining elements, we have to compare the element in the pathChange array just above and just to the left, and see which one is smaller. The reason we only compare these two is because, in the instructions, we can only ever move down and to the right. So, using Math.min() and the same logic as before, we will add the smaller of the pathChange elements (either the one from above or from the left) to the value of that element in the grid.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  pathChange[0][0] = grid[0][0];

  for (let i = 1; i < m; i++) {
    pathChange[i][0] = pathChange[i - 1][0] + grid[i][0]; 
  }

  for (let i = 1; i < n; i++) {
    pathChange[0][i] = pathChange[0][i - 1] + grid[0][i];
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      pathChange[i][j] =
        Math.min(pathChange[i - 1][j], pathChange[i][j - 1]) + grid[i][j];
    }
  }

  //...
}

Now, pathChange is complete. Because our target square is the one in the bottom right corner, we can just return the value at that point in the pathChange array.

function minPathSum(grid) {
  const m = grid.length;
  const n = grid[0].length;
  const pathChange = new Array(m);
  for (let i = 0; i < m; i++) {
    pathChange[i] = new Array(n);
  }
  pathChange[0][0] = grid[0][0];

  for (let i = 1; i < m; i++) {
    pathChange[i][0] = pathChange[i - 1][0] + grid[i][0]; 
  }

  for (let i = 1; i < n; i++) {
    pathChange[0][i] = pathChange[0][i - 1] + grid[0][i];
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      pathChange[i][j] =
        Math.min(pathChange[i - 1][j], pathChange[i][j - 1]) + grid[i][j];
    }
  }

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

Walking Through an Example

I like using examples and visuals in order to better explain and understand tricky algorithms like this one. I'll start an inputted grid:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
.
The first few lines of the function establish m, n, and pathChange. Once pathChange is created in the size of the input array, we have a grid of size m x n, which is all filled out, as well as pathChange, which is the same size as the inputted grid, but is empty.

Two grids: the input 'grid', which is filled with the inputted values, and 'pathChange', which is the same size but empty

Now, we set pathChange[0][0] = grid[0][0].

Grid stays the same, but pathChange now has one value at [0][0], which is 1. pathChange now equals [[1,<empty>,<empty>], [<empty>,<empty>,<empty>], [<empty>,<empty>,<empty>]].

Next, we go down the first column, and set each item equal to the last item in pathChange plus that location's value in the grid.

Arrows down the first column show the values that are being added. Each item in the first column of pathChange equals the sum of the previous value in pathChange plus that value in the grid. pathChange now equals [[1,<empty>,<empty>], [2,<empty>,<empty>], [6,<empty>,<empty>]].

We'll do the same thing for the first row: set each item in pathChange equal to the last item in pathChange plus that location's value in the grid.

Arrows across the first row show the values being added. Each item int he first row of pathChange equals the sum of the previous value in pathChange and the value of that element in the grid. pathChange now equals [[1,4,5], [2,<empty>,<empty>], [6,<empty>,<empty>]].

Now is time for the nested for loops. At the square [1][1] in pathChange, we will set it equal to the minimum of (2,4) plus 5, which means 2 + 5.

Using circles in grid and pathChange to demonstrate which items are being compared. The value of the current square in pathChange becomes 7. pathChange now equals [[1,4,5], [2,7,<empty>], [6,<empty>,<empty>]].

Now, at the square [1][2] in pathChange, we set it equal to the minimum of (5, 7) + 1.

Using circles in grid and pathChange to demonstrate which values are being compared. The value of the current square in pathChange becomes 6. pathChange now equals [[1,4,5], [2,7,6], [6,<empty>,<empty>]].

At the square [2][1], we set it equal to the minimum of (6, 7) + 2.

Using circles in grid and pathChange to demonstrate which values are being compared. The value of the current square in pathChange becomes 8. pathChange now equals [[1,4,5], [2,7,6], [6,8,<empty>]].

Finally, at [2][2], we set it equal to the minimum of (6, 8) + 1.

Using circles in grid and pathChange to demonstrate which values are being compared. The value of the current and therefore final square in pathChange becomes 7. pathChange now equals [[1,4,5], [2,7,6], [6,8,7]].

And there's our expected output! Let me know in the comments if you have any questions or alternate approaches.

Algorithm of the Day (33 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 31 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays

Posted on May 21 by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide