Path Finding with Dynamic Programming

Let's take a step back.

Imagine you're navigating a maze, and each cell in the maze offers you a reward. Your aim is to find the path from the starting point to the destination that maximizes these rewards. This is like a treasure hunt, except you're gathering coins or gems along the way.

The Aha Moment: A Single Principle

Let's crystallize our approach with a powerful observation:

If the richest path passes through a cell at (r, c), then the path leading up to (r, c) and the path leading away from (r, c) to the goal must also be the richest.

Picture it as a road trip where you have multiple stops. If a city along your route is the richest in terms of tourist attractions, the route to that city and beyond must also offer the most attractions.

Breaking Down the Problem

We've essentially divided a big challenge into two smaller tasks:

1. Finding the Richest Path to (r, c): What's the best route from the start to this cell?
2. Finding the Richest Path from (r, c) to Goal: What's the best route from this cell to the destination?

Combine these, and voila, you have your ultimate treasure-rich path.

The Role of Memoization

Just like you'd mark checkpoints on a map, we'll mark the richest path to each cell in a matrix called reward. This matrix will store the maximum accumulated reward from the starting cell to every other cell on the grid.

Two Key Matrices

• Input Matrix $w[r,c]$: This holds the reward for each individual cell at (r, c).
• Memoization Matrix $\text{reward}[r,c]$: This stores the maximum accumulated reward from the start to each cell (r, c).

Think of the first matrix as the list of tourist attractions in each city, and the second matrix as your travel diary, recording the best experiences up to each point.

By the end of this exercise, the cell in reward corresponding to the goal will hold the maximum reward possible. Just follow the path back, and you've solved the maze in the most rewarding way.