2.2.4. Column by Column Computation

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

In this section, we define 'paths(i, j)' as the total number of paths from the starting point (0, 0) to a given point (i, j) on a grid. To find paths to any point (i, j), we recognize that there are only two ways to approach it: from the left neighbor (i, j-1) or from the neighbor below (i-1, j). Therefore, we can calculate the total paths to (i, j) by adding the paths to (i-1, j) and (i, j-1). Mathematically, this is expressed as: paths(i, j) = paths(i-1, j) + paths(i, j-1). Hence, knowing the paths to the points leading into (i, j) is essential to solving for paths to (i, j) itself.

Imagine you are trying to navigate a grid city. To get to a park at point (3,3), you can either walk from a restaurant directly to the left at (3,2) or from a coffee shop directly below at (2,3). Each time you reach (3,3), you either take one step left from (3,2) or one step up from (2,3). The total number of ways you can reach your park combines the number of ways you could have arrived at those two previous spots.

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.

Boundary conditions refer to special cases in our grid where we don't have all neighbors available for calculating paths. For example, in the leftmost column (like (0,0), (1,0)), the only possible way to come into those points is from below since there is no option to approach them from the left side. Similarly, for the topmost row (like (0,0), (0,1)), the only way to get to those points is from the left neighbor, which implies that the paths are defined differently at the boundaries of the grid.

Think of it as being in a tall building where the only way to get to the first floor from the ground is to take the stairs up from the bottom. If you were looking to get upstairs to the second floor and there are no stairs to your left, the only option to get there is by climbing straight up from the ground floor. The boundary conditions ensure that we correctly set paths based on the limited movements we can make at the edges of 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 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.

When there are holes in the grid, we can manage them by simply assigning a value of 0 to paths(i, j) where there is a hole. This means that no paths can go through that point, effectively cutting off any potential paths from both above or below that hole. As we calculate paths for other points, if they would connect to a hole, we do not count those paths, ensuring that the number of accessible paths remains correct.

Imagine walking on a well-paved path that suddenly has a blocked area due to a construction site. Even if you could reach the blocked area from two different directions, you cannot walk through it—just like we cannot count any paths that lead to a hole in our grid.

Now, when we go to the next row, likewise this 0 contributes only 0. So, above it, because no paths can come through this, this direction, the number of paths coming here is only 6 coming from the left.

Dynamic programming and memoization are related but differ in implementation. Dynamic programming involves systematically filling out a structure (like our grid) by computing all possible subproblems in a specific order. In contrast, memoization is more about saving previously computed results to avoid recalculations. Dynamic programming can ensure that we systematically account for each point in the grid, while memoization tries to reduce the number of calls but can lead to inefficiencies in some scenarios.

Consider two students trying to solve math problems: one (dynamic programming) writes down every answer in a systematic table and avoids redundancy by calculating everything step-by-step, while the other (memoization) only recalls previously solved problems and tries to skip unnecessary steps but might miss crucial understanding if those problems weren't reused effectively.

However, as we said before, dynamic programming is iterative. It is going to be just the simple, memoization is going to be recursive.

Dynamic programming operates through an iterative process, where we solve all subproblems in a sequence, ensuring that each relevant value is computed in the correct order. On the other hand, memoization relies heavily on recursion, meaning it will call itself multiple times for the same values unless we store them in a lookup table. While memoization can be simpler to implement directly from recursive definitions, dynamic programming requires more consideration of the problem structure to ensure efficient processing.

Think of dynamic programming as a relay race, where each runner completes their leg in a specific order, passing the baton smoothly. Memoization, however, resembles a cataloging process in a library, where finding a book requires going back to the shelf (recursion) rather than collecting them in order as they arrive.

--