2.1.3. Initial Conditions

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 - 1) I can make one step right and come to (i,j) or from (i - 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.

In this chunk, we explore how to analyze paths on a grid. There are two allowed movements: right and up. To understand how to get to a point (i, j), we recognize that we can arrive there either from the left neighbor at (i, j - 1) or from the below neighbor at (i - 1, j). Each path extending into (i, j) comes from these two points. Thus, the total paths to (i, j) can be calculated by considering all paths arriving from these neighbors. This understanding sets up a foundation for recursive and inductive reasoning which will be used to calculate routes through a grid.

Imagine navigating through a city grid. You can move east or north, and you're trying to figure out how many different routes you can take from your starting position (0,0) to reach a specific destination, let's say (3,2). You can visualize each position on the grid as an intersection and each way of reaching it as a different route. To get to your destination, you'd count all the routes available from the intersections just before yours.

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 -1,j) and the paths to (i,j -1). So, there are, of course, some boundary conditions. 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.

In this section, we define paths(i, j) as the total number of ways to reach point (i, j) from the start point (0, 0). Using the inductive analysis, we see that paths to (i, j) can be computed by summing the paths that arrive from the point directly below it (i - 1, j) and the point directly to the left (i, j - 1). This formula will be used to calculate paths throughout the grid, taking into account that the edges of the grid have specific conditions, such as the leftmost column only being reachable from the left.

Think of this as building pathways in a community park. Each point represents a spot in the park, and you can only walk from one spot to another either straight from your left or below. The number of paths to reach a picnic area (i,j) depends on how many paths lead to the spot directly beside it and the spot directly below it. If a path leads nowhere, it's like having a dead end – it contributes zero toward reaching the picnic area.

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.

In this part, we discuss the initial condition at the starting point (0, 0). The only way to stay put is to simply remain where you are, which means there's exactly one way to be at this point. This is crucial because if we incorrectly assigned this to be zero, it would disrupt the calculations across the entire grid, leading to no valid paths. This initial condition thus serves as the foundation upon which further calculations will be built.

Imagine a game where you're standing still at your starting line, and the only option is to remain there. You cannot move in any direction, but this 'no movement' state is still considered a valid position – there is just one way to be there: to stay. If we consider that there could be zero ways to be at the start, it would feel like you never truly began the game.

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 paths(i,j) to 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.

In this section, we address how to manage 'holes' or unavailable paths in our grid. If a specific point (i, j) is considered a hole, it will contribute 0 possible paths. This means that despite the paths that might lead to this point from its neighbors (both above and side), it cannot be traversed, and thus should not be counted toward the total. This rule will propagate through the grid and impact how we count paths leading to other points potentially still reachable.

Consider a construction area in a park with blocked walkways where workers are doing maintenance. If you encounter one of these areas, you can't proceed through it. No matter how many paths exist leading to this point, since it’s blocked, all paths leading to it effectively count as 0 because you can’t walk through it.

The difficulty with this calculation is the same as involved with the Fibonacci, which is, that if I have a particular calculation, say for example, supposing we start a recursive calculation at (5,10), then this will ask for (4,10) and (5,9). Now, these in turn will both ask for (4,9), so (4,9). if I just evaluate this paths function recursively, the way it is returning, the inductive definition, it will end up calling paths of (4,9) at least twice from this and this wasteful recomputation will occur throughout and we will get an exponentiation number of calls to paths.

This chunk introduces the inefficiencies associated with purely recursive approaches, specifically illustrating how paths can be redundantly recalculated. For example, if we recursively find the number of paths to (5, 10), we may end up recalculating paths to (4, 9) multiple times, leading to an exponentially growing number of calculations. This reiterates the need for optimization techniques in managing computational complexity, such as dynamic programming methods.

Imagine you're trying to calculate the total number of routes to your friend's birthday party (5, 10), but as you explore all paths, you realize you keep getting stuck at the same traffic intersections (4, 9). Each time you hit that intersection, you remember how many ways led to it. Instead of counting it anew each time, you should jot down that number – this will save time and effort on your journey.

--