Source code online books for professionals by professionals

Listing 8-14.  Memoized Recursive Function for Expected Optimal Search Cost
def rec_opt_tree(p):
    @memo
    def s(i,j):
        if i == j: return 0
        return s(i,j-1) + p[j-1]
    @memo
    def e(i,j):
        if i == j: return 0
        sub = min(e(i,r) + e(r+1,j) for r in range(i,j))
        return sub + s(i,j)
    return e(0,len(p))
 
18
You could certainly design some sort of cost function so this wasn’t the case, but then we couldn’t use dynamic programming  
(or, indeed, recursive decomposition) anymore. The induction wouldn’t work.
19
You should have a whack at the matrix chains yourself (Exercise 8-18), and perhaps even the parsing, if you’re so inclined.

---

Chapter 8 
■
 tangled dependenCies and MeMoization 
183
All in all, the running time of this algorithm is cubic. The asymptotic upper bound is straightforward: There is a 
quadratic number of subproblems (that is, intervals), and we have a linear scan for the best root inside each of them. 
In fact, the lower bound is also cubic (this is a bit trickier to show), so the running time is 
Θ(n
3
).
As for the previous DP algorithms, the iterative version (Listing 8-15) is similar in many ways to the memoized 
one. To solve the problems in a safe (that is, topologically sorted) order, it solves all intervals of a certain length k 
before going on to the larger ones. To keep things simple, I’m using a dict (or, more specifically, a defaultdict, which 
automatically supplies the zeros). You could easily rewrite the implementation to use, say, a list of lists instead.  
(Note, though, that only a triangular half-matrix is needed—not the full n by n.)