2.3.2. Efficiency of Memoization

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

To understand how to reach a specific point on a grid, consider the ways to arrive at point (i,j). There are only two possible directions to come from: the left (i,j-1) or below (i-1,j). Therefore, any path originating from the start point (0,0) can extend to (i,j) either from the left or from below by taking one additional step. This leads us to define a recursive relationship for calculating the number of paths to any point on the grid based on where they come from.

Think of it like navigating a maze. If you're at a certain position, your only options might be to move left or up (or in a different context, perhaps right or down). Each choice you make allows you to explore new paths, just like deciding which way to turn at each corner encourages you to find a way out of the maze.

So, let us write paths (i,j) to denote the number of paths from (0,0) to the current point (i,j). 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.

The expression paths(i,j) is defined as the total number of paths from the starting point (0,0) to the target point (i,j). More specifically, the value for paths(i,j) is calculated by adding the number of ways to get to the point directly above it (i-1,j) and the point directly to the left of it (i,j-1). However, there are boundary conditions to consider; for instance, if you're in the leftmost column or the bottom row, paths might only be computable from a single direction since there are no points on one side.

Imagine you're walking on a city grid. If you're walking along the eastern edge (the right side) of the city, you can only move in one way to get to your destination: by moving south or west. This is similar to how paths are counted on a grid in programming; the routes available to you depend heavily on your current location.

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.

In a grid scenario where certain points are 'holes' or inaccessible, we declare that the number of paths to these points is zero. This means that no paths can pass through these points, effectively breaking any routes that would include them. The value 'paths(i,j)' will be set to 0, and this will propagate to neighboring points, affecting the overall path count calculations nearby.

Think about walking through a garden maze where some pathways are blocked off with fences. When you encounter a fence, you know you can't go that way, which means those pathways leading through the fence are essentially useless. Just as you would circumvent those obstacles in the maze, the algorithm simply skips over those holes when calculating potential paths.

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 the wasteful recomputation will occur throughout.

The complexity arises from the recursive nature of our approach, akin to calculating Fibonacci numbers. For instance, starting from point (5,10) requires the results of its two immediate predecessors (4,10) and (5,9). However, both of these also depend on (4,9), which means we end up calculating the same value multiple times—a clear inefficiency in the process. This repeated calculation leads to an exponential growth in the number of calls made.

Imagine you are trying to bake a layer cake, but each layer requires you to first boil water. If you've already boiled water for the first layer, but you need to do it again for the second layer, you end up wasting time repeating tasks that don’t need to be repeated. Just like in our path calculation, some of the efforts are redundant and can be eliminated.

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.

Memoization is a technique used to optimize recursive algorithms by storing the results of expensive function calls and returning the cached result when the same inputs occur again. In our case, if we have already calculated the number of paths to a given point (i,j), we store that value to prevent redundant calculations in subsequent calls.

Think of memoization like a travel log. If you've already noted the best route to a particular destination, you wouldn't want to refigure it every time someone asks. Instead, you'd refer back to your notes to get the answer quickly. Similarly, memoization allows a program to save previously computed paths so it doesn't waste time recalculating them.

The other way 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.

Dynamic programming is an optimization strategy that involves breaking down problems into simpler subproblems, solving each subproblem just once, and storing the solutions. It differs from memoization in that it works iteratively instead of recursively and builds the solution in a bottom-up manner. Thus, the entire grid can be computed efficiently without redundancy.

Consider a project where you need to build a large structure. Instead of attacking the entire structure at once (like recursion), dynamic programming would have you first establish the foundation and build layer by layer, ensuring that everything is in place before moving on. This not only makes the task simpler but also more efficient by avoiding unnecessary complications.

--