2.2. Using Dynamic Programming on the Grid

So, let us ask ourselves the following question. How do I get to a point (i,j) on the grid? So, I claim, that given our structure, there are only two ways I can come here. I can either come right from the neighbor on my left or from (i minus 1, j), I can go up once there. So, if I have any paths, which starts at (0,0), any path, which comes to (i,j -1), can be extended in a unique way to (i,j). Likewise, any path, which comes from (0,0) to (i-1,j) can be extended in a unique way.

This chunk introduces the concept of how to navigate through a grid to reach a specific point (i,j). It explains that you can reach any point on the grid either from the left neighbor (i,j-1) or from the below neighbor (i-1,j). Each path leading to these neighbors can be uniquely extended to reach point (i,j). Thus, to find how many paths lead to (i,j), one must consider the number of paths leading to its neighboring points.

Imagine you're trying to navigate through a maze (the grid) to reach a treasure (point (i,j)). You can only move right or up. If you're at a point and want to reach the treasure, you can either come from the left path or the path below you. Just like counting how many different routes you could take based on the directions you have available.

So, let us write paths (i,j) to denote the number of paths from (0,0) to the current point (i,j). The paths to (i,j) are the sum of paths to (i minus 1,j) and the paths to (i,j minus 1). There are boundary conditions for the leftmost column and the bottom row where values are determined only from a singular direction.

This chunk establishes the core function for computing the number of paths: the paths leading to point (i,j) are the sum of paths leading from the left and below. Boundary conditions are clarified here, indicating that on the leftmost column, paths can only come from the left, and on the bottom row, they can only come up from below.

Think of a team building a road from one point to another, where they can only come from the north or the west. The total number of routes to any point is simply the total routes taken by teams coming from the northern road plus those from the western path.

How do we deal with holes in this setup? That is easy, we just declare paths(i,j) be 0 if there is a hole at a given point. This will automatically propagate to its neighbors correctly.

In this portion, the text discusses how to handle obstacles, or 'holes', in the grid. If a grid point contains a hole, the number of paths leading to that point is set to zero, which impacts the paths to its neighbors. This zero value prevents any paths from continuing through that point.

Imagine a road that suddenly has a large pothole rendering it unusable. Any driver attempting to take a route that includes that road must reroute. Similarly, in our grid, if a point is a hole, it blocks all paths leading through it.

The difficulty with this calculation is that if I evaluate this paths function recursively, wasteful recomputation will occur throughout and we will get an exponentiation number of calls to paths. Two technologies to deal with this are memoization and dynamic programming.

This section contrasts the inefficiency of naive recursive solutions with memoization and dynamic programming. It highlights that naive recursion can lead to excessive calculations (duplicating work) due to the repeated computation of the same paths. Memoization is a method to store computed results, whereas dynamic programming emphasizes computing in an iterative manner based on dependency.

Consider a student rewriting the same essay multiple times. If they stored their previous drafts (like memoization), they could save time. Dynamic programming would be akin to creating an outline to ensure they systematically cover all topics without redundant rewriting.

How would we use dynamic programming on the grid? This is our grid with holes. First, identify DAG structure of the dependencies. We start at (0,0) and fill the value there, which is 1, then compute row by row or column by column to fill in the values based on previously computed values.

This part explains the practical steps for applying dynamic programming to compute the number of paths in the grid with holes. It emphasizes setting up a directed acyclic graph (DAG) for dependencies, which ensures that each point's value is computed based on its neighbors. The process is iterative, allowing for efficient computation by progressing through the grid either row by row or column by column.

Envision building a structure like a house: you can't build the roof before the walls are up. In a grid, we compute paths logically, ensuring each section is built upon the previous sections, whether we move left to right (row by row) or down (column by column).

--