2.1.4. Handling Holes

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

In this part, we are defining a way to calculate the number of paths to any point (i, j) on a grid based on paths leading from two specific directions: from the left (i, j-1) and from below (i-1, j). This leads us to conclude that the total number of ways to reach (i, j) is the sum of the paths to those two neighboring points. It is crucial to understand that boundary conditions like the first row and column must be addressed separately since they might not have all neighbors.

Imagine you are trying to navigate blindly from your house at (0, 0) to a friend's house at point (i, j) using a strict rule: you can only move right or up. Every time you reach a point, you look behind you to see where you came from (left or below). You can only count the paths that got you there based on those previous steps!

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 is a hole on the grid at any position (i, j), we can simply declare that the number of paths leading to that point is 0. This means that no routes can go through that hole, effectively stopping any paths that might have used that point. The idea illustrates how a hole affects neighboring points, where those points’ potential paths must also consider that the hole blocks their route.

Think of a hole in a walking path in a park. If a hole appears, you cannot walk through it, and it would prevent you from moving forwards (or upwards) if that path was part of your route. For instance, if your plan was to walk straight ahead to get to a lake but a hole appears, you’d have to find a new way around it.

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

When calculating paths recursively, we may face re-computation of the same path, which increases the number of function calls substantially. For instance, computing the paths to (5, 10) requests paths from (4,10) and (5,9), but both of those also require the same previous point (4,9). This repetition can create inefficiencies and lead to exponential calls while computing the result.

Think of a group project where everyone is tasked to gather certain information. If two people keep returning to the same individual for the same data instead of sharing, they end up wasting time by asking the same questions over and over, rather than working efficiently as a team.

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 its left and bottom neighbor.

Dynamic programming helps efficiently manage the calculation of paths by avoiding repetitive computations through a structured approach. By recognizing that each point (i,j) is dependent on its left and bottom neighbors, we can design a directed acyclic graph (DAG) that illustrates these dependencies clearly. This allows us to systematically compute paths in a bottom-up manner.

Imagine building a house where each floor depends on the previous one. If you try to build the roof without the first floor, it wouldn’t work. Similarly, using a structured plan helps us avoid missing any crucial steps in building our paths by addressing every dependency systematically.

So, if we do this value, then automatically this dependency go. So, we will be able to do this value, when this will go, so we can do this value and so on. So, we can compute the entire bottom row...

By using topological sorting, we can fill the grid row-by-row (or column-by-column). Once we compute the paths leading to a point, we can easily compute the paths leading to the next point in line efficiently. This process continues until we reach the end of the grid while properly handling the holes along the way, ensuring that those points contribute 0 wherever necessary.

Picture filling up a bucket from a water source. If you’ve placed a block in the bucket (the hole), the water cannot flow through that block effortlessly, but you can still fill up the areas around it. You need to know where to pour and in which order to ensure the water (paths) fills the bucket accurately.

So therefore, the memo table will have a linear number of entries, right. It will have, say, 2 m plus 2 n entries. It will only have the outer boundary of this grid. Whereas dynamic programming will have n times an entry.

The difference between memoization and dynamic programming primarily lies in how they compute values. Memoization computes values as needed in a top-down fashion and captures only the necessary entries, while dynamic programming computes all possible entries in advance from a bottom-up perspective. This results in memoization storing less in its table compared to dynamic programming’s complete grid entry computation.

Think of memoization like packing your bag for a trip only with items as you remember to need them, whereas dynamic programming is like packing everything you’ll need based on a checklist before you leave. It might take more effort, but you'll be more prepared by covering all bases.

--