2.3.1. Effect of Holes on Computation

Try these first

1. 1.

   What is the base case for paths at (0, 0)?

   Hint

   Consider how many ways you can stay at the origin.

2. 2.

   If there is a hole at (1, 1), what will paths(1, 1) equal?

   Hint

   Think about how many paths can reach a hole.

3. 3.

   What condition states that paths equal zero?

   • When paths are from below
   • When there is a hole
   • When summing paths

   Hint

   Remember the definition of a hole in the grid.

4. 4.

   Dynamic programming builds solutions in what manner?

   • True
   • False

   Hint

   Analyze the structure of dynamic programming.

5. 5.

   Given a 5x5 grid with holes at (2, 2) and (3, 3), outline a path-finding algorithm that utilizes dynamic programming to calculate how to reach (4, 4).

   Hint

   Create your table based on a structure where you check left and below for computations.

6. 6.

   Create a memoized function to compute paths in a 3x3 grid, explaining how you avoid repeated calls.

   Hint

   Think about the strategy for storing results to prevent re-evaluation.