2.3.3. Conclusion on Dynamic Programming

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, every path from (0,0) to (i,j) can be extended in a unique way.

To understand how to reach a point (i, j) on a grid using dynamic programming, we start at the top left corner, (0,0). From any point (i,j), you can arrive from either directly left (i,j-1) or directly below (i-1,j). This leads to the key idea that the total number of paths to (i,j) can be determined by the sum of the number of paths to its left and the number of paths to below, formalized as paths(i,j) = paths(i-1,j) + paths(i,j-1).

Imagine you are trying to find your way through a maze. You can only move up or to the right, similar to our grid. To reach your destination (i,j), think of the possible previous steps: you could have just come from your left or below. The idea of counting all possible ways to get to each point is like figuring all the possible routes you could take in the maze from the start to your final spot.

There are, of course, some boundary 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.

Boundary conditions refer to the edges of the grid, where only one path typically exists. For instance, if you are in the leftmost column (0,j), you can only move from the point below (1,j) and cannot come from the left since it doesn't exist. Similarly, if you're in the topmost row (i,0), you can only come from the left (i-1,0). Additionally, the base case (0,0) has exactly one way to stay put.

Think of a one-way street where cars can only flow in one direction. At the start of this street (the top left corner), there are no alternate paths, just a single route that leads to the next point. If you're at the edge of a lake (the edges of the grid), you can only go in the direction where there is land, illustrating the concept of boundary conditions effectively.

So, how do we deal with holes in this setup? ... if there is a hole at some point, then this thing is going to contribute 0 regardless of what is above or below.

When dealing with obstacles or holes in the grid, if a point is marked as a hole, the number of paths reaching that point is set to zero. This means even if there are potential paths leading to that hole, they become irrelevant. As you calculate paths to neighboring points for holes, any contribution from paths that lead to holes is disregarded.

Imagine planning a party where you have to navigate a backyard full of obstacles like a swimming pool (the holes). If a pathway leads to the pool area, it's blocked; hence, you can't count it as a route. Similarly, the calculations for paths to a 'hole' in the grid are zero, effectively marking those routes as unusable.

So, we have two technologies to deal with this... This is what we call dynamic programming.

Memoization and dynamic programming both aim to optimize calculations by avoiding redundant work. In memoization, the program stores the results of expensive function calls and returns the cached result when the same inputs occur again, primarily using recursion. In contrast, dynamic programming evaluates all sub-problems iteratively, ensuring all dependencies are resolved before computing a particular path count, making it efficient for larger datasets.

Imagine you're studying for an exam. If you use memoization, you rely on recalling facts when you encounter similar questions, saving effort but sometimes missing insights. Dynamic programming, however, is like systematically building knowledge by learning each concept step by step before tackling complex problems, ensuring a deeper understanding and less redundancy.

So, therefore, though this looks like a wasteful dynamic programming strategy... the extra work usually pays off.

While dynamic programming may seem inefficient at first because it computes many values that are never used (due to holes or obstructions), its iterative nature often leads to faster overall computations. This efficiency arises because it systematically solves and caches all sub-problems once, allowing for quick retrieval instead of repeated calculations from the ground up as in recursion.

Consider a factory that produces parts. With a dynamic programming approach, the factory optimizes the assembly line to ensure every part is produced efficiently in bulk even if some parts may be defective. The initial investment in resources seems wasteful, but ultimately leads to higher productivity and quicker outputs as repeated fixes are eliminated.

--