2.2.1. DAG Structure of Dependencies

So, as you might guess, since we are looking at these kind of inductive formulations and recursive programs, what we are really looking for is the inductive formulation of the grid path. 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, which is, that we can go right or we can go up, there are only two ways I can come here. I can either come right from the neighbor on my left. So, from (i,j minus 1) I can make one step right and come to (i,j) or from (i minus 1, j), I can go up once there. So, if I have any paths, which starts at (0,0),...right. So, every path from (0,0) to i minus, (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 the unique way, right.

In this chunk, we are exploring how to navigate a grid based on allowable movements, which are right and up. The example points (i,j) refer to the coordinates on the grid. The author explains that there are only two possible previous positions from which one can arrive at any point (i,j): from the left (i,j-1) or from below (i-1,j). This means that to find the total number of paths to (i,j), you add the paths leading to those two previous points. Therefore, the solution builds on smaller sub-problems to determine the total paths to the desired point.

Imagine you are navigating a city on a grid layout where you can only move north or east. To reach a particular intersection, you could come from the intersection directly below or directly to the left. Counting all possible routes to that intersection would involve summing the unique routes leading to those two intersections!

So, let us write paths (i,j) to denote the number of paths from (0,0) to the current point (i,j). So, what we have just seen from our inductive analysis on the problem is, that if you are at (i,j), then the paths come from left or from below. So, the paths to (i,j) are the sum of paths to (i minus1,j) and the paths to (i,j minus1). So, there are, of course, some boundary conditions.

Here, the author specifies a function 'paths(i,j)' that represents the number of unique paths from the starting point (0,0) to any point (i,j) on the grid. As discussed in the previous chunk, the total paths to (i,j) are derived by adding paths from (i-1,j) and (i,j-1). The mention of boundary conditions introduces the scenarios at the edges of the grid where one of the neighbors does not exist – for example, the leftmost column or the top row, where paths can only originate from one side.

Think of standing on the bottom row of a grid and trying to reach the top right corner, where you have to follow a set path without stepping off the edges. If you go left or up, you can only reach certain points, similar to how paths are calculated based on existing routes in the grid.

So, how do we deal with holes in this setup? That is easy, we just say, that whenever there is a hole at a given point we just declare parts of ((Refer Time: 11:52)) be 0. In other words, if there is a hole at some point, then this thing is going to contribute 0 regardless of what is above or below.

This chunk addresses how to manage obstacles, or holes, in the grid which would hinder movement. The author states that if a grid point has a hole, the total number of paths leading to that point should be set to 0, as no paths can go through it. This has the cascading effect of setting paths to surrounding points based on the presence of a hole, ensuring that these obstacles propagate through the calculation.

Imagine you are on a hiking trail that has a washout, which prevents you from walking through that part of the trail. Just like the calculator tracks paths around obstacles, you need to find an alternative route. If you can't go through that washout area, any route attempting to go through it doesn't count, as it’s simply not a viable path.

So, how would we use dynamic programming on the grid? So, this is our grid with the two holes at the (2,4) and (4,4). The first thing is to identify DAG structure of the dependencies, right. So, it is, we know, that every (i,j) depends on, it is left and bottom neighbor.

This section changes focus to dynamic programming, explaining that the first task is to understand the Directed Acyclic Graph (DAG) architecture that represents the dependency of paths on prior calculated points in the grid. It explains that each node in this DAG structure captures the conditions under which paths can be followed, specifically highlighting that every point (i,j) will rely on its left (i,j-1) and below (i-1,j) points.

Visualize a construction project where each step needs the previous one completed before moving forward. Similarly, in our grid, every point must 'wait' for its dependencies from the left and below to be determined before it can be calculated. It's like building a wall – you can’t place a brick on top until the bottom layer is secure.

--