2.2.2. Row by Row Computation

Try these first

1. 1.

   If you are at (0,0), how many paths are there to (0,0)?

   Hint

   Consider what it means to stay in the same place.

2. 2.

   Name two ways you can reach the point (2,1) in a grid starting from (0,0).

   Hint

   Think about moving in increments of 1.

3. 3.

   What is the formula for calculating paths to point (i,j) in a grid?

   Hint

   Think about where you can move to reach (i,j).

4. 4.

   True or False: In a grid with holes, all path values are affected by zero values.

   • True
   • False

   Hint

   Consider the flow of paths in relation to holes.

5. 5.

   Given a 5x5 grid with holes at (2,2) and (3,3), write a function to compute paths from (0,0) to (4,4) programmatically. Show your results for multiple layouts of holes.

   Hint

   Map out the grid with a two-dimensional array for ease.

6. 6.

   Describe a scenario where using memoization might fail compared to dynamic programming when adding complexity (like adding more holes or larger grid sizes).

   Hint

   Consider performance and time with increasing complexity in problem.