Already from the headline of problem 81 of Project Euler it sounds familiar, so lets jump right in to it

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by

only moving to the right and down, is indicated in bold red and is equal to 2427.

131673 234 103 18 20196342965 150 630 803 746422111 537 699 497 121956 805 732 524 37331Find the minimal path sum, in matrix.txt (right click and ‘Save Link/Target As…’), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

This is one of the most classic examples of problems which can be solved using dynamic programming. We have already solved Problem 15 where we used a sort of dynamic programming approach to traverse a grid to find the number of paths through the grid. We also solved problem 18 with dynamic programming to find the minimum path through a triangle.

## Dynamic Programming

I know we have been through this before, but since we will be dealing with exact grid over the next couple of problems I would like to cover it again.

Dynamic programming can be used when we are able to make smaller problems which we can solve and the reuse the solution when we are solving the main problem.

In this case, if we are standing in a specific point, no matter how we got there we can calculate the minimum path from there and to the goal. And since we can only go down and right we can disregard all the cells above and to the left when looking for the minimal solution – which is exactly why dynamic programming works. This is also known as optimal sub structure as I elaborate on in Problem 18.

## Illustrating the solution

If we want to find the minimal solution for the path from a specific cell to the goal we can choose one of two paths *down* or *right*. Assuming we know the minimal path from both the cell below and from the cell to the right we can rather easy choose between the going *right* and going *down*.

So how do we find this solution? Well if you are on the bottom row next to the goal it is pretty easy to add the two since the minimum path is obviously to go to the right to get to the goal.

This can then be done for all the bottom row as well as the the right row. Now that we know the minimum paths from the black cells we can see that we can find the solution to the grey number since we know the minimum solution to both the cell to the right and below of that cell.

Since we know that the minimum path from the cell to the right is 1287 and the minimum path from the cell below is 368, going down from the grey cell would be the better choice since we want to minimize the solution. So that minimum path from the grey cell is 121 + min(1287,368) = 489.

This can be continued for all cells working us up to the top left cell in which case we will now the cost of the minimum path through the matrix.

## Implementing the solution

Now that we have the general idea we can implement the solution rather easily in C# as

int[,] grid = readInput(filename); int gridSize = grid.GetLength(0); //calculate the solution for bottom and right for (int i = gridSize - 2; i >= 0; i--) { grid[gridSize - 1, i] += grid[gridSize - 1, i+1]; grid[i,gridSize - 1] += grid[i+1, gridSize - 1]; } for (int i = gridSize - 2; i >= 0; i--) { for (int j = gridSize - 2; j >= 0; j--) { grid[i, j] += Math.Min(grid[i + 1, j], grid[i, j + 1]); } }

which runs in

In the 80x80 grid the min path is 427337 Solution took 3,2962 ms

So we can find the minimal solution in 3ms even though there is a total of paths through the matrix.

## Wrapping up

This is the classical example of dynamic programming. You should get the idea from the description as well as the previously solve problems.

As always you can find the source code here including the method for reading the input file and a method for print the array to check the current state.

Why are you publishing the answers to project Euler questions ?

Hi Jack

I do it for the same reason I do search for solutions my self after finding a solution. To figure out if I have missed something in making a smart solution. And if that is the case I would like at least a pointer to the field of mathematics or computer science needed to solve the problem.

So my hope is that people who are interested in this kind of problems learn something new and get even more interested in finding the “right” solution instead of just “a” solution.

I guess I could avoid posting the actual answer, but I am unsure whether that is what you refer to.

/Kristian

Hi Kristian,

Nice blog

I think I understand the solution (well, didn’t look at the code but read the above briefly). I have a few questions.

basically you suggest to start from right bottom and “climb” up to left top, correct?

another question:

what if the numbers were as so:

422 10

980 956

37 331

the right solution is to go up to 956 and not left to 37

even if the sum (37+331) is less than (956+331).

and by your explanation above I couldn’t understand how it solves the problem.

thanks in advance,

Yair.

It is not completely correct. I suggest starting from the bottom and make a new grid. The entry in each cell is the minimum value to get from that place in the original grid and to the bottom corner.

In your case It would require several steps. The first one looking like

- -

- -

- 331

That is trivial. The next step we can calculate the bottom left and the right in the middle since they can only move in one direction. This gives us a grid looking like

- -

- 1287

368 331

Now we can calculate the upper right corner and the middle left. The upper right only have one possible way so that value will be 1287+10 = 1297. The middle left can go either down or right, so we will choose the smallest one which is down. So the value to go from that spot to the bottom right is 368+980 = 1348 giving us

- 1297

1348 1287

368 331

Now we can calculate the upper left where we can choose to go down or right. Since the sum to the right is the smallest that is the way to go giving us a result of 1297+422 = 1719.

I hope this clarifies things.

Thank you!

most helpful, And it does clarify my questions.

thanks again.

Great, glad I could make some sense to it. And I completely forgot to say thanks for the compliment.

Hi, I tried this program the same way your explanation describes it, or at least I think I did. But when my code runs I get the value of 563261. My method is similar to that of number 18. It went from bottom right to top. I’m having a hard time understanding why this does not work. If you emailed me I could send you my code if you like.

Thanks!

Why don’t you post the code here, or on pastebin for that matter. That way everyone can chip in and help you out.

Ok, here is my code.

http://pastebin.com/raw.php?i=yGF5HcHi

Hello Sam.

I think there is something you’re misunderstanding. You seem to be greedily picking the minimum path, instead of using dynamic programming. What that means is that on each step you go to the next possible square in the grid that has the minimum value. This is not optimal, and will usually not result in the correct answer. If you add the following to your

FindBestPathmethod:then you can see that your program only visits 158 squares, while an optimal algorithm always needs to visit all the 80*80 squares (otherwise, how would it know that there is not another path that is better?).

I suggest you study the above post better, and try to fix your solution. Let us know if you aren’t able to fix it.

You probably already know this, but if you look at the algorithm closely, you don’t even need to store the whole new grid, only the previous line. And if you start from the top left, you can read the values as you go.

Doing so takes your algorithm from quadratic to linear space complexity, which doesn’t matter here since the problem is small, but it is crucial in live, big-scale applications.

I hadn’t thought of that really. But yes you are absolutely right.

Hey Kristian ,

Can you explain why the greedy algorithm doesn’t work in the problem, as in the code of Sam ?

Bjarki explains it as a such. But to elaborate a bit more. Sam takes the minimum value of the step immidiatly down or to the right. However, this does not necessarily the path that leads to the minimum solution.

To make an exagerated example take the example

1 1 8

2 9 9

2 2 2

If you stand in the upper left corner and take the minimum value of the right or down you will move along the upper and right most barrier and get a total sum of 21. However the minimum is at the left and lower boundary which would give us a total of 9.

I hope this explains it.