2.3. Illustration of Memoization vs Dynamic Programming

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.

In a grid where one can only move right or up, to determine how to reach a specific point (i, j), you need to know the number of paths coming from its left neighbor (i, j-1) and its bottom neighbor (i-1, j). You can think of each point in the grid as a junction where you must decide where to go next. At (i, j), the only two possible paths are from the left or below, meaning knowing how to reach those points informs how many ways there are to reach (i, j). This leads to the recursive formulation of paths where the total number of paths to (i, j) equals the sum of the paths to (i-1, j) and (i, j-1).

Imagine navigating a city grid where you can only walk north or east. To get to a restaurant, you can approach it either from the west (left) or from the south (below). Each street represents a path, and to know how many paths lead to the restaurant, you need to count those leading to the streets adjacent to it.

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

The inductive formulation you create leads to a recursive structure where paths to (i, j) are essentially built from paths to two specific points: its left neighbor and its bottom neighbor. Base cases need to be carefully established, especially for the edges of the grid. For example, the leftmost column (0,0) to (i,0) can only be accessed from below since there is no left neighbor present. Conversations about base cases are essential as they provide foundational values needed to build other calculations. Starting from these points makes it possible to calculate paths in other parts of the grid efficiently.

Consider building a ladder: each rung (or point in the grid) depends on the previous rungs below it for support. If the first rung (base case) isn’t there, the rest can't exist. Similarly, on the grid, if points along the boundary aren't properly defined, it interferes with calculating the entire structure.

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

In scenarios where there are holes or blocks in the grid, these physical barriers impact how paths can be calculated. A hole at (i, j) means that no paths can originate from or pass through this point; hence, you would define the number of paths to that point as 0. This definition not only simplifies calculations but also propagates downward to its neighbors, where paths from the blocked point will always be inherited as 0. Therefore, when designing your recursive or dynamic program, you must define how these holes influence calculations to avoid miscounting paths.

Think of a street with a blocked road (the hole). If there’s a 'road closed' sign, no vehicles can pass, meaning all routes leading to that point must reroute elsewhere. In terms of grid calculations, any attempt to compute paths through that blocked road will yield no successful routes.

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.

Memoization and dynamic programming are two strategies for solving recursive problems efficiently. Memoization involves caching previously computed values (like paths) to avoid redundant calculations. On the other hand, dynamic programming approaches the problem iteratively by understanding the relationship between subproblems and calculating those values in a systematic order. This often leads to fewer total operations because you’re directly solving necessary computations rather than navigating through potentially repeating calculations.

Imagine studying for an exam. Using memoization would be like revisiting your notes each time you want to remember a fact, ensuring you don’t forget what you’ve memorized. Dynamic programming, however, resembles learning incrementally; you might study by starting with foundational concepts and then building upon them systematically, allowing for more efficient retention and understanding.

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. … If you remember, if these depends on the two values, left and below, we draw an edge from the left to this node and from below to this node.

When applying dynamic programming to the grid, the first step is to analyze how each point depends on others. The points in the grid can be represented as a Directed Acyclic Graph (DAG), where edges indicate dependencies. You start from the beginning point (0,0) and work your way toward the end point systematically, ensuring all necessary prior paths have been accounted for. This creates a clear pathway for computations, avoiding costly repeated calculations.

Think about assembling furniture. You need to follow the instructions step-by-step (like working from the grid). Each piece depends on the previous pieces being assembled correctly. So you can't install the tabletop before the legs – just like you can't calculate the paths to (i, j) without first knowing the paths to (i-1, j) and (i, j-1).

So, therefore, the memo table will have a linear number of entries, … Whereas, dynamic programming will have n times an entry will have. Every grid point will be computed in the table even though most of them are useless. … Therefore though this looks like a wasteful dynamic programming strategy in case the holes are distributed in a bad way.

The key difference between memoization and dynamic programming can be quantified in terms of efficiency. Memoization only computes necessary values as needed, usually resulting in fewer entries. In contrast, dynamic programming aggressively computes paths for all grid points including those that may never be used (due to being blocked by holes), leading to more computations overall. While dynamic programming may seem wasteful when holes block pathways, it tends to be more efficient in pure runtime because of its iterative nature and ability to systematically build results as calculations advance.

It’s akin to packing for a trip. Using memoization would involve only bringing the clothes and items you know you will wear or use, while dynamic programming might mean packing everything just in case you might want to wear a specific outfit even if that outfit isn't likely to be worn due to weather constraints. The second method might take more time and resources but potentially results in a more thorough preparation.

--