Project Euler 81 - Path Sum: 2 Ways

Official link: https://projecteuler.net/problem=81

Harder Version of Problem 67

Thought Process

I solved this one with dynamic programming, which to me is one of the most difficult topics to understand so I will try to explain in depth with a bit of a step by step guide for what my algorithm is doing.

My algorithm goes through a input matrix and will build the shortest path from top left to bottom right, by updating cells with the shortest path to those cells for example for the given matrix after the algorithm is done the following cells look as such:

[0,0] = 131
[0,1] = 804
- Only one way from [0,0] -> [0,1]
[1,0] = 332
- Only one way from [0,0] -> [1,0]
[1,1] = 428
- Way 1: [1,0] -> [1,1] which would be 332 + 96 = 428
- Way 2: [0,1] -> [1,1] which would be 804 + 96 = 900, so we choose the smaller one

Let's see what going on here, there is a double nested loop going through the matrix row by row with 4 if statements

The given matrix goes from 0 to 4

Given a co-ordinate [i,j] if i-1 >= 0 and j-1 >= 0 then means we are not on the first row or column, because if we were then either i = 0 or j = 0
- This means that we need to take the minimum of the block above us and to the left of us
If the first condition fails, then we must be on the first row or first column. We deal with first column, if we are on it then the we can only take a path from the cell above us
Similarly first row we can only take to the left of us
The fourth condition is only for the first cell of the entire matrix

Through this process we continuously update the matrix with the shortest path to the current cell [i,j] therefore the final cell will be the shortest distance from [0,0] to [x-1,y-1] (See definition for x and y in code)

Interactive Code

Nothing interactive here, please try and mess around with this code and see if you understand how the matrix is updating.

A great exercise is to try and build the matrix up from bottom right to top left in the same way to see if you've really understood the code

Page updated

Google Sites

Report abuse