How do I program this? Path Optimization

A smart monkey is, of course, always trying to collect as many bananas
as possible. The setting this time is that there is a m-by-n matrix with
positive integer entries indicating numbers of bananas. The monkey starts
at the left-top corner (i.e., 1st row 1st column) and should eventually arrive
at the right-bottom corner (i.e., mth row nth column). The rule is that
the monkey could only move to the right or down, and will only collect
these bananas that are on his path. Suppose the monkey knows the entire
matrix before he starts. Can you help him design an optimal path?
For our case, let us use m = n = 20. Assume that matrix elements are
independently chosen from 1 to 9 uniformly (this is not necessary but just
for your convenience). You should first generate the matrix randomly and
store it in a variable called A,

My idea is to take the box with more bananas however i don't think i can reach the opposite corner with that.

I'd appreciate your help..

Answer 1

[Walter Roberson]

Of course you can reach the opposite corner with that, as long as you add the condition that if you are at the right edge then you must go down, and that if you are at the bottom edge then you must go right. You can demonstrate easily enough that the total path will always be (m - 1) + (n - 1) -- no more, no less.

You will find that the locally-greedy algorithm is not optimal.

x 1
0 0
2 0
2 0

the step with most bananas is the one to the right, collecting 1 banana, but having done that the path must be downward through 0 bananas, total 1 banana collected. The step from x down towards 0 gets fewer bananas immediately but allows proceeding down twice more, collecting 4 bananas, before heading right at the last step.

You can model the system by using dijkstra's algorithm on a directed graph.