Illustration of Memoization vs Dynamic Programming

Let's begin by understanding how many unique paths we can take to reach the point (i,j) on a grid. Remember, we can only come from either the left or below, which means we consider the points (i,j-1) and (i-1,j).

So, if I want to calculate the paths to (i, j), I just need to know how many paths lead to the points directly beside it?

Exactly! If we call the number of paths to (i,j) as paths(i,j), then we have: paths(i,j) = paths(i-1,j) + paths(i,j-1). And don’t forget the boundary conditions!

What happens if we hit a hole in the grid?

Great question! If there's a hole at a point, we declare paths(i,j) to be 0, meaning no path can go through that point. This will propagate to its neighbors.

Wait, so if that point is zero, what does that do to the paths around it?

Well, if one neighbor is zero, it actually turns into a restriction or a barrier. For instance, if paths(i-1,j) is a 0, then paths(i,j) only depends on the other valid direction!

In summary, remember, every time you think about reaching a new point, you must consider its two neighbors and whether they allow for valid paths. Let's move on to how to compute these paths efficiently.

Now, let’s differentiate between two powerful techniques: memoization and dynamic programming. Can anyone explain what memoization is?

Isn't it when you save the results of function calls to avoid re-computation?

Exactly! You store the results, so when you need the same value, it's retrieved directly from memory instead of recalculating it. And dynamic programming?

That’s when you systematically break down problems into subproblems and solve them without recursion?

Yes! It's iterative and helps solve all subproblems, even if you don’t need every result. This approach fills out a table, while memoization could skip some values.

But isn’t it inefficient sometimes, computing values that won't be used?

Good point! However, the structured approach of dynamic programming can lead to better overall time efficiency in many cases compared to recursive memoization, which has its call overhead.

To wrap up, remember memoization stores results based only on need while dynamic programming computes systematically. Keep that contrast in mind.

Let’s apply dynamic programming to compute the number of paths in our grid with some holes. Can anyone guide us on the first step?

We should start at the origin point (0,0) and initialize it with a value of 1 because there's one way to stay in place.

Correct! Now, how do we move forward in our grid from here?

We can fill in the first row and then the first column since those only have one path originating from either the left or the below position.

Exactly! And what about the holes? How do we handle those as we compute?

If we hit a hole, we simply mark the number of paths to that point as zero, right?

Right again! So we continue this process row by row, ensuring each computation takes into account the possibility of holes.

To conclude this session, when using dynamic programming, fill the grid progressively while considering paths dependencies and boundary conditions. Keep practicing!