Dynamic Programming: Finding Optimal Paths
Yesterday, I sat through a code challenge comprised of three questions. After having some success with the first two- the third problem in the test had me somewhat stumped, an (extremely) analogous problem is written below:
The Problem
A grid of size N*M (i.e. N rows and M columns) is given. Each square of the grid can be indexed using a pair of integers (A,B) where 0≤A < N and 0≤B < M. A machine is located initially at field (0, 0). It can perform two kinds of moves:
Move from the field (A,B) to field (A+1,B)
or
Move from the field (A,B) to field (A,B+1)
During its movement across the grid, it collects all the coins from the square it lands on.
Write a function that, given a matrix of size N*M describing the number of coins lying on each square of a N*M-sized grid, returns the maximal number of coins the machine can collect while moving from the square (0, 0) to the square (N−1, M−1) in the manner specified above.
My Initial Attempt
While I don’t have the code for my initial attempt, something similar (with less consideration for edge cases and the like) to my work might look something like this: