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)
.