2.3.1. Effect of Holes on Computation

So, let us look for a better solution. 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, any path, which somehow comes to (i,j -1), then by taking one, exactly one step, that path becomes one path to (i,j) 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. So, if I count the task coming to the two neighbours, then each of those paths can be extended to reach the current node. So, therefore, I get the inductive formulation as follows.

The section begins with a look at how to formulate a solution for reaching a certain point on a grid using inductive reasoning. The main idea is that from any point (i, j) on a grid, there are only two ways to come to that point: from the left neighbor (i, j-1) or from the below neighbor (i-1, j). This leads to the conclusion that the total number of paths to reach (i, j) from the starting point (0, 0) can be calculated as the sum of the number of paths coming from these two neighbors. This establishes a foundational relationship on how paths can be extended from neighboring points to reach the target point.

Think of a game where you are moving on a chessboard, starting from the bottom left corner. To reach any square on the board, you can only move up or right. This situation is similar to the grid path calculation where each square can only be accessed through the squares to its left or below it. By counting all possible moves from these two directions, you can figure out how many ways you can reach your desired square.

So, if you look at our grid, in general, then if we look at the leftmost column, let us start the bottom row. So, we start the bottom row, right, then we know, that this is of the form (0,0), then (1,0) and so on to (5,0), right. So, anything of the form (i,0) derives its value only from the left because there is no corresponding row from the left. Similarly, from the leftmost column, from this (0,0), (0,1) and so on up to (0,15). And now, there is nothing from the left. So, I can only get it from j-1 from the row below. And finally, you have to ask ourselves what happens at the initial conditions. So, if I am at (0,0) and I want to go to (0,0), how many ways are there? Well, this is a trivial path, there is only one way, by just staying there. It is important that it is not 0 because remember, that if it is 0, then everywhere you are just adding things and nothing will come, you will get no paths.

This section discusses the boundary conditions for the grid path calculations. On the grid's leftmost column and bottom row, the number of paths is influenced only by what is directly available from the left or below. For example, in the bottom row, moving from (0, 0) up to (i, 0) has only one path option—moving straight from left to right since there's no upper neighbor. The initial condition is emphasized, where there is only one way to stay at the starting point (0, 0), which is crucial to preventing zero paths elsewhere in the grid.

Imagine you are in a straight hallway (the bottom row) where you can only continue walking forward. Since there are no doors on the sides, you can only choose to walk straight. Similarly, if someone asks how many ways to stay in the same spot in the hallway, the answer is just simply '1'—by not moving at all!

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. So, if I come, if I have something coming from here and here I will just ignore it and say this is 0. And likewise, when I compute thing about there will be some value x coming from the left. So, this will just be x plus 0. And similarly, over here there will be something coming from below, say y, and this will be 0+y, right. So, any hole will just have by declaration paths (i,j) equal to 0 because nothing can go through it and this will automatically propagate to its neighbors correctly.

This chunk explains how holes in the grid impact the calculation of paths. When a point on the grid has a hole, it doesn't contribute to any path leading to it, meaning the path count for that point is set to zero. This rule applies regardless of any valid paths coming from neighboring points. As a result, when you reach a hole, it cascades through the calculations, causing all neighboring paths that depend on it to also reflect a reduction in total paths. This effectively means that any point blocked by a hole will not serve as a valid pathway in the grid.

Consider an obstacle or barrier placed along pathways in a park. If you are moving from one side to another, but there’s a fence blocking your path, you can’t pass through it, thus your route calculations need to account for that barrier. In calculations, this represents a hole, with affected paths being reduced to zero since they can't traverse through that conflicting point.

So, we have seen before, we have two technologies to deal with this. So, one is memoization where we just make sure that we have never paths (i,j) the same value of i and j more than once. The other way is to, is to anticipate the sub problems, figure out how they depend on each other, then solve them directly iteratively in a suitable order and this is what we call dynamic programming.

In this section, we distinguish between two techniques to tackle path computations: memoization and dynamic programming. Memoization is a technique in which we store the results of previously computed paths to avoid recalculating them. In contrast, dynamic programming emphasizes understanding the dependencies between various subproblems and solving them in a structured manner. Instead of recalling past calculations recursively, we iteratively fill out an entire grid or table, making the process more efficient and straightforward as we work our way up from known base cases.

Imagine preparing a multi-course meal. If you use memoization, you might keep notes on how many ingredients you've already measured while making sure not to re-measure those ingredients again. With dynamic programming, it’s like having a detailed recipe that outlines the precise order of how to combine each dish step-by-step, ensuring you systematically account for everything without omission.

So, finally, before we conclude, let us just look at an instructive illustration of the difference between a memoization and dynamic programming. So, if we have a bunch of holes which are along the border, then intuitively what it says is, that if I start from here and I go anyway like this, I am going to get stuck, ok. So, if I start my memoization from there, then everywhere it is just going to see a 0. So, all these values are going to be 0, and memoization is not going to look further around these. So, memorization, I claim, is only going to look along this outer boundary.

This portion clarifies the practical implications of using memoization over dynamic programming, especially in grids with boundaries affected by holes. When using memoization, if it encounters a boundary that leads to a hole, it tends to freeze paths to those points because it’s designed to only follow known values. Thus, many potential paths get ignored due to being trapped by zeros. Conversely, dynamic programming would systematically compute values for all grid points, ensuring any path leading toward a hole is recorded, even if those paths ultimately yield no viable routes, thereby capturing the full landscape of the problem.

Think of a video game where the player can only reach certain areas based on previously cleared sections. If a new obstacle is discovered (a hole), the player's strategy might change drastically. While a player utilizing memoization would only look to navigate the edge of obstacles, a dynamic programming player would simultaneously explore all options and strategize future levels of the game, even analyzing paths that lead nowhere.

--