title: Generating an optimal binary search tree (Cormen)
body: <p>I'm reading Cormen et al., <em>Introduction to Algorithms</em> (3rd ed.) (<a href="https://github.com/yuanhui-yang/Introduction-to-Algorithms/blob/master/Introduction%20to%20Algorithms%20-%203rd%20Edition.pdf" rel="noreferrer">PDF</a>), section 15.4 on optimal binary search trees, but am having some trouble implementing the pseudocode for the <code>optimal_bst</code> function in Python.</p>
  
  <p>Here is the example I'm trying to apply the optimal BST to:</p>
  
  <p><a href="https://i.stack.imgur.com/HZ3rG.png" rel="noreferrer"><img src="https://i.stack.imgur.com/HZ3rG.png" alt="enter image description here"></a></p>
  
  <p>Let us define <code>e[i,j]</code> as the expected cost of searching an optimal binary search tree containing the keys labeled from <code>i</code> to <code>j</code>. Ultimately, we wish to compute <code>e[1, n]</code>, where <code>n</code> is the number of keys (5 in this example). The final recursive formulation is:</p>
  
  <p><a href="https://i.stack.imgur.com/3vXly.png" rel="noreferrer"><img src="https://i.stack.imgur.com/3vXly.png" alt="enter image description here"></a></p>
  
  <p>which should be implemented by the following pseudocode:</p>
  
  <p><a href="https://i.stack.imgur.com/HbPJH.png" rel="noreferrer"><img src="https://i.stack.imgur.com/HbPJH.png" alt="enter image description here"></a></p>
  
  <p>Notice that the pseudocode interchangeably uses 1- and 0-based indexing, whereas Python uses only the latter. As a consequence I'm having trouble implementing the pseudocode. Here is what I have so far:</p>
  
  <pre><code>import numpy as np
  
  p = [0.15, 0.10, 0.05, 0.10, 0.20]
  q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10]
  n = len(p)
  
  e = np.diag(q)
  w = np.diag(q)
  root = np.zeros((n, n))
  for l in range(1, n+1):
      for i in range(n-l+1):
          j = i + l
          e[i, j] = np.inf
          w[i, j] = w[i, j-1] + p[j-1] + q[j]
          for r in range(i, j+1):
              t = e[i-1, r-1] + e[r, j] + w[i-1, j]
              if t &lt; e[i-1, j]:
                  e[i-1, j] = t
                  root[i-1, j] = r
  
  print(w)
  print(e)
  </code></pre>
  
  <p>However, if I run this the weights <code>w</code> get computed correctly, but the expected search values <code>e</code> remain 'stuck' at their initialized values:</p>
  
  <pre><code>[[ 0.05  0.3   0.45  0.55  0.7   1.  ]
   [ 0.    0.1   0.25  0.35  0.5   0.8 ]
   [ 0.    0.    0.05  0.15  0.3   0.6 ]
   [ 0.    0.    0.    0.05  0.2   0.5 ]
   [ 0.    0.    0.    0.    0.05  0.35]
   [ 0.    0.    0.    0.    0.    0.1 ]]
  [[ 0.05   inf   inf   inf   inf   inf]
   [ 0.    0.1    inf   inf   inf   inf]
   [ 0.    0.    0.05   inf   inf   inf]
   [ 0.    0.    0.    0.05   inf   inf]
   [ 0.    0.    0.    0.    0.05   inf]
   [ 0.    0.    0.    0.    0.    0.1 ]]
  </code></pre>
  
  <p>What I expect is that <code>e</code>, <code>w</code>, and <code>root</code> be as follows:</p>
  
  <p><a href="https://i.stack.imgur.com/EPxz7.png" rel="noreferrer"><img src="https://i.stack.imgur.com/EPxz7.png" alt="enter image description here"></a></p>
  
  <p>I've been debugging this for a couple of hours by now and am still stuck. Can someone point out what is wrong with the Python code above?</p>