PyPE solution to PE problem 81
PyPE solution to PE problem 81
Blueprint information
- Status:
- Complete
- Approver:
- None
- Priority:
- Undefined
- Drafter:
- None
- Direction:
- Needs approval
- Assignee:
- None
- Definition:
- Approved
- Series goal:
- None
- Implementation:
- Implemented
- Milestone target:
- None
- Started by
- Scott Armitage
- Completed by
- Scott Armitage
Related branches
Related bugs
Sprints
Whiteboard
ProjectEule
===
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.
131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331
Find 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.
Solution
--------
We begin at the apex (0,0) and work our way down and right, recursively
traversing the grid. Each time we calculate the maximum sum at a given
co-ordinate, we cache the value for future use. This is very similar to
the solution used for problem 18, only with a grid instead of a triangle.
Since we are looking for a minimum, we cannot instantiate our search results
to 0; we must instead instantiate them to a number larger than we will ever
see. We call this `big_s` (for big-sum). If big_s is not given, it is taken
to be the maximum value in the grid multiplied by the area of the grid.
Answer
------
427337