Introduction to Programming in Python, Aug-Dec 2014
                          Assignment 8
                 Due Saturday, 29 November, 2014

----------------------------------------------------------------------
NOTE: The usual rules apply about file names for submitting your
      assignment.
----------------------------------------------------------------------

Filename: memodp.py

Dynamic Programming
-------------------

Given a sequence of matrices M_1, M_2, ..., M_n with dimensions
(r_1,c_1), (r_2,c_2), ..., (r_n,c_n) such that c_i = r_i+1 for i
in range(1,n), we can write an inductive solution to find the
optimal way of bracketing the expression M_1 x M_2 x ... x M_n to
minimize the total number of operations required to compute the
final product.  (The recurrence was discussed in the last lecture
in the course.)

Write two functions:

1. matmultmemo(dimlist)

   Computes the answer using memoization.

2. matmultdp(dimlist)

   Computes the answer using dynamic programming.

In both cases, the argument dimlist is a list of pairs
[(r_1,c_1),...,(r_n,c_n)] containing the dimensions of
M_1,...,M_n, with c_i = r_i+1 for i in range(1,n).

======================================================================