2.1.1. Paths to (i,j)

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 this chunk, we're examining how to reach a specific point (i,j) on a grid. The key idea is that movement is restricted to either moving right or moving up. From (i,j), one can only arrive from the left neighbor (i,j-1) by taking one right step or from the bottom neighbor (i-1,j) by taking one upward step. Thus, for every unique path that leads to either of those neighbors, we can extend it by one step to reach (i,j).

Think of a simple grid as a city block, where you can only walk along the streets that go either north or east. If you want to get to a store located at the corner of a block (i,j), you can only arrive there from the person coming from the block directly west of you or the block directly south of you. This illustrates how paths are formed in our grid model.

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 minus 1,j) and the paths to (i,j minus 1).

Here, we define a function paths(i,j) which signifies the number of ways to travel from the starting point (0,0) to (i,j). Based on our previous understanding, the total number of paths to (i,j) can be calculated by adding the number of paths coming in from the left (i,j-1) and the paths coming in from below (i-1,j). This creates a recursive relationship that allows us to compute the total paths efficiently.

Imagine a game where you need to collect treasures located at various points on the board. Each point can be reached only by stepping into it from the left or from below. To figure out how many ways there are to reach a specific treasure, you simply add up all the ways to get to the treasures directly next to it!

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

Boundary conditions refer to the special cases at the edges of the grid. For any point in the leftmost column (like (i,0)), the only way to reach it is from the point directly to its left; since there are no points above it, those values depend solely on the leftward neighbors. Similarly, points in the topmost row can only be reached from below, relying on information from the previous row.

Using our earlier city block analogy, think of a street that runs along the edge of a lake. If you want to reach points on the edge of the lake (the first column), you can only step to those points by moving directly from another point on the same street to the left, since there’s no road leading up from the lake.

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

The initial condition checks how many unique ways we can begin our journey at the starting point (0,0). Since there's no movement involved, the only way to 'get to' (0,0) is to simply remain at that spot. Thus, we define paths(0,0) = 1 to establish a solid foundation for calculating paths to other points in the grid.

Imagine you are standing still in your living room; you can say there's exactly one way to be in your living room without moving! This establishes your starting point for any adventures you plan to take to get to different rooms—or squares in our 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) 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.

Holes in the grid represent obstacles that block any possible path. When a hole exists at a location (i,j), we set paths(i,j) to 0 because no paths can pass through it. This condition ensures that while calculating the total paths, any path attempting to go through that hole will be effectively ignored, thereby propagating zero values to any cells dependent on it.

Consider a blocked road in the city that prevents any travel. If there’s a construction zone at a particular intersection (like a hole), no one can pass that way! Hence, it effectively becomes zero pathways for anyone trying to access areas that rely on this route.

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.

This segment outlines two techniques for optimizing how we calculate paths: memoization, which stores already computed values to avoid repeating calculations, and dynamic programming, which takes a broader approach. Dynamic programming involves analyzing how sub-problems relate and solving them in a systematic sequence so that each problem is addressed just once.

Think of memoization like jotting down your previous steps in a recipe so you won’t have to figure them out again. In contrast, dynamic programming is like preparing all the ingredients before you start cooking—having everything organized and ready allows you to cook efficiently without doubling back.

--