Comment by graycat
4 hours ago
Glanced at the exercises. It appears that two of them have numbers arranged in a triangle and ask for a longest path.
Hmm. Given such a triangle, let m be the largest number in the triangle. For each x in the triangle, replace it with m - x. For the resulting triangle, solve it to give the shortest path using one of the well known network shortest path algorithms.
> Hmm. Given such a triangle, let m be the largest number in the triangle. For each x in the triangle, replace it with m - x.
By the time you've actually done these two steps, you could have already finished the problem with a dynamic programming approach.
(Starting from the bottom row and working upward, replace each cell in the row with the length of the longest path from itself to the bottom, which you can know by checking which of its two children has the longer path associated.)