Recitation 9

Code for number of paths

DP and memoization code for counting the number of "paths" in an n*n grid.

Here a path is like the one from the previous lecture: Start at some cell in the top, and at each row, choose a cell touching (either below, below and to the left, or below and to the right) the cell chosen in the previous row.

Matrix Chain Multiplication

Given a chain of matrices (of varying sizes) computer the optimal order to multiply them in. See CLRS 15.2 (page 331) for details.