2.1.2. Boundary Conditions

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.

In this chunk, we define 'paths(i,j)', which symbolizes the total number of paths leading to the point (i,j) from the starting point (0,0). According to the inductive formulation, the paths to reach (i,j) can only originate from two neighboring points: directly to the left, (i,j-1), or directly below, (i-1,j). Therefore, we can summarize this in a mathematical formula: paths(i,j) = paths(i-1,j) + paths(i,j-1). This equation indicates that the total paths to (i,j) are the sum of the paths to its left and below neighbors, effectively creating a recursive relationship amongst the grid points. Furthermore, it's highlighted that there are boundary conditions, which means we need to consider cases when we are at the edges of the grid.

Think of it like navigating through a city grid. If you want to get to a specific address on the grid by moving only to the right or up, you can only arrive there by coming from either the left block or the block below. Just like a map where you can only travel straight up or right, your path choices are limited, and you must account for which blocks you have already passed through to determine how many ways you can reach your destination.

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).

In this section, we focus on identifying boundary cases in the grid. The leftmost column (like (i,0), where 'i' varies) can only derive its number of paths from the neighboring cell to the left. Since there's no cell on the left for these points, they cannot be reached from any previous point. Similarly, the cells in the uppermost row (like (0,j)) derive their paths only from the cell immediately below them, since, like in the column case, there’s no row above them to derive from. Therefore, all cells along the left edge and top edge are special boundary cases where the paths have defined ways of being calculated based on their positions.

Imagine you are standing at the far left end of a straight street. The only way to get to the next block is to step forward from where you are; there’s no other block to your left to come from. Similarly, if you start on the top edge of a street and you can only move downwards, your navigation choices are limited based on where you are standing. These boundaries in the street analogy help us understand that movement in certain directions depends on previous positions.

So, 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 segment, we consider the initial condition, which is essential for establishing the base of our path counting. When starting at (0,0), there is only one way to 'travel' to (0,0), which is by staying put; this single state is crucial because it establishes that we have at least one valid path. If we declared this value as zero, mathematically, it would imply that there are no paths leading outwards or from this initial state, making any further calculations redundant as they'd all yield zero paths.

Think of this as starting a game at the starting line. No matter what, you are there, and you can only start your journey from this exact point. There’s no way to not be at the starting point; being there is already your first step. If we pretend you aren't there, then the whole game becomes impossible, as you need that initial position to have any chance of progressing.

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 (i,j) be 0.

In this chunk, we address a challenge when navigating a grid that contains 'holes', or inaccessible points. When a hole exists at (i,j), we simplify our calculations by declaring that the number of paths to that square is zero (paths(i,j) = 0). This means that no paths can pass through that point, effectively making it a barrier. The importance of this declaration is that it propagates to neighboring points; that is, any calculations for paths leading to this point will disregard paths that would have crossed over the hole, thus maintaining the integrity of our path-counting solution.

Visualize playing a board game where certain squares are 'forbidden'. If you land on one of those squares, you cannot proceed through that space. You need to navigate around these barriers, and those forbidden squares dictate your path choices, just as the holes in our grid restrict valid pathways.

The difficulty with this calculation is the same as involved with the Fibonacci, which is, that if I have a particular calculation...this wasteful recomputation will occur throughout and we will get an exponentiation number of calls to paths.

This chunk discusses the inefficiencies associated with recursive calculations when using an inductive approach, particularly highlighting the analogy with the Fibonacci sequence. When calculating paths using recursion, the program may revisit the same state multiple times, resulting in repeated calculations, leading to exponential growth in function calls and inefficient performance. To overcome this, we employ methods such as memoization, which avoids recalculating previously solved subproblems by storing their results, and dynamic programming, which organizes calculations iteratively based on dependencies of subproblems.

Consider trying to bake a multi-layer cake. If you wrote down the recipe for each layer every time without referencing a saved version, you'd waste time repeating steps unnecessarily. However, if you note down each step and its outcomes for future reference, you streamline the process, just like memoization optimizes recursive calls efficiently.

--