# What's the most rewarding path?

Get from the top-left to the bottom-right using only right and down moves. Pick up as much gold as possible. There is only one maximum.

• If there were a lateral tag, I'd think the numbers 6 and 9 are "G"olds (as the relation between the numbers and golds is not mentioned). – WhatsUp Nov 11 '19 at 14:58

It is a 10x10 map and you need to go east 9 times and south 9 times. There are total $${18\choose9}$$ = 48620 paths which are impractical to be done with pen and paper in a reasonable amount of time.
But if you observe

If I know the best answer (max gold) that can be collected until the cell on my north and cell on my west, I should perhaps always choose greedily because those two answers are optimal.

This can be done pretty quickly with just 10x10=100 calculations.

109 (Assuming my unverified calculations are correct)

Proof of work

Method

Write the cumulative sum of the first row and column (Blue)
For every other cell, write the sum of that cell and maximum of the top cell and cell to the left and mark the source with an arrow.
The last cell contains the answer. Use arrows to reach the source recursively until you reach the top cell.

• This method always finds the optimal answer, even in cases where the greedy algorithm does not. It's a pity that for the given grid the greedy algorithm also mostly works, apart from the ambiguity at the cell with score 100. – Jaap Scherphuis Nov 11 '19 at 7:17
• It's called dynamic programming (done by hand). We used to have this sort of problems in math contests for children. – WhatsUp Nov 11 '19 at 14:53

@Mohit Jain's solution is nice and provably correct. It also shows you the best way to reach any square from the top left corner.

I happened to solve the puzzle in a way that's pretty much identical, but in reverse.

Both methods are equally valid, but somehow I felt that finding the optimum path from any square to the bottom right might be a more interesting "side effect" of solving the puzzle, so I decided to post my solution too, so here it is:

Start at

the bottom right, and mark the best possible score for its neighbours.

Then continue in the same manner throughout.

Like this:

and going on,

And then you make an error because single digit addition is hard, and after backtracking, you finally reach the top left corner (again):

And now you have the optimal score for every starting square, and to find the best path to the bottom right you can always just go to the neighbour with the better score.

At the risk of flogging a dead horse, I wanted to solve it using Dijkstra's algorithm, since an answer implied that it required a computer to do so.

First, we change it to a minimize problem. We know that all solutions use 19 steps, so we simply change the values to $$10-x$$ and then minimize the result:

Initialize the top left to a value of 1. Everywhere else is value infinity. Then we just check the lowest, unvisited nodes and move on one step.

The above is after a handful of steps. Visited nodes have been circled and need not be looked at again. The unvisited nodes have the total value that it took to get there. We choose the one with the lowest value (21 in this case) for the next step. In this case, it goes to the right and that node gets a value of 23.

We then do the same again for the unvisited nodes of 22. Then 23, marking them as visited (circled) in each case:

Here we've gone as far as 30. Note that we take the lowest total value if necessary. In this particular problem, it was not really necessary (there was one (literal) corner case, where I counted the corner two steps as one):

Here we've finished it:

The minimum value is 81. To convert back to the maximum value, we undo our transformation ($$190-81=109$$). Phew!

To figure out the path, we work backwards from the last node. It has total value of 81 and a value of 8, so it must have come from a 73. There's only one node with 73. It has a value of 7, so must have come from a 66. Again only one node does it. Repeat all the way:

Local maximum solution:

Consider we should always choose larger value while pick either right or down move as next step(if both values are same, join the next 2 steps into consideration), the local maximum from start to end is: $$9\downarrow6\to8\downarrow8\downarrow3\to7\to9\to4\to6\downarrow7\downarrow3\downarrow6\to7\downarrow8\to5\downarrow4\to4\to3\downarrow2 = 109$$

And consdier from end back to the start, the local maximum is: $$9\downarrow6\to8\downarrow8\downarrow3\to7\to9\downarrow3\downarrow5\to8\to3\downarrow6\to7\downarrow8\to5\downarrow4\to4\to3\downarrow2 = 108$$

But there should exist an optimal maximum, still verifying the algorithm :P
Remark: This solution could be solved by Dijkstra's algorithm, but this may need computer to easy-solved, however this puzzle requires no-computer.

• I also approached the same way, and found the same solution of 109, but only reason I did not post it as an answer is : this approach does not necessarily yield the maximum solution. For example, consider the 3X3 table with the rows as : [ 1, 2, 1] , [0, 3, 4], [9, 2, 3]. The current approach says the optimum path is 1 + 2 + 3 + 4 + 3 = 13 whereas the actual optimum is 1 + 0 + 9 + 2 + 3 = 15 – SamRoy Nov 11 '19 at 6:11
• @SamRoy Yes, so it's only local but not optimal solution, and Dijkstra's algo. could find out the optimal but handy work may be lousy if no computer used... – Conifers Nov 11 '19 at 6:20
• I also wrote a computer program which gives 109 as the maximum reward, and the same path you mentioned. But I guess there is no general rule to find out the optimal solution by analytical approach only – SamRoy Nov 11 '19 at 6:22
• For a reference, it's not a Dijkstra algorithm but Dynamic Programming approach instead (shown by @MohitJain) -- In your local optimum one, it's Greedy approach. The Dijkstra is to find the shortest path given the lengths of each segments of path (edges). – athin Nov 11 '19 at 6:45
• @athin we could turn the value as the weighted edge and find the maximum path, may like the Dijkstra's but a twisted(Just thought in mind, need transformation proofs.) – Conifers Nov 11 '19 at 6:50