Mark As Completed Discussion

Finding the Path With Maximum Reward

Suppose we have a robot that is placed at cell (0, 0) of an m * n grid. The robot has to navigate the grid and reach its goal position, while collecting a reward from each cell it passes through. The aim of navigation is to follow a path that maximizes the reward through the grid. The only legal moves allowed are an "up" move and a "right" move.

This tutorial on dynamic programming has an informative illustration on how to find a path through a grid to maximize reward. Both time complexity and space complexity of the dynamic programming solution are O(m * n).