title: Optimal Search Tree Using Python - Code Analysis
body: <p>First of all, sorry about the naive question. But I couldn't find help elsewhere</p>
  
  <p>I'm trying to create an Optimal Search Tree using Dynamic Programing in Python that receives two lists (a set of keys and a set of frequencies) and returns two answers: </p>
  
  <p>1 - The smallest path cost.</p>
  
  <p>2 - The generated tree for that smallest cost.</p>
  
  <p>I basically need to create a tree organized by the most accessed items on top (most accessed item it's the root), and return the smallest path cost from that tree, by using the Dynamic Programming solution.</p>
  
  <p>I've the following implemented code using Python:</p>
  
  <pre><code>def optimalSearchTree(keys, freq, n):
      #Create an auxiliary 2D matrix to store results of subproblems
      cost = [[0 for x in xrange(n)] for y in xrange(n)]
  
      #For a single key, cost is equal to frequency of the key
      #for i in xrange (0,n):
      #    cost[i][i] = freq[i]
  
      # Now we need to consider chains of length 2, 3, ... .
      # L is chain length.
      for L in xrange (2,n):
          for i in xrange(0,n-L+1):
              j = i+L-1
              cost[i][j] = sys.maxint
              for r in xrange (i,j):
                  if (r &gt; i):
                      c = cost[i][r-1] + sum(freq, i, j)
                  elif (r &lt; j):
                      c = cost[r+1][j] + sum(freq, i, j)
                  elif (c &lt; cost[i][j]):
                      cost[i][j] = c
  
      return cost[0][n-1]
  
  def sum(freq, i, j):
      s = 0
      k = i
      for k in xrange (k,j):
          s += freq[k]
      return s
  
  keys = [10,12,20]
  freq = [34,8,50]
  n=sys.getsizeof(keys)/sys.getsizeof(keys[0])
  print(optimalSearchTree(keys, freq, n))
  </code></pre>
  
  <p>I'm trying to output the answer 1. The smallest cost for that tree should be 142 (the value stored on the Matrix Position [0][n-1], according to the Dynamic Programming solution). But unfortunately it's returning 0. I couldn't find any issues in that code. What's going wrong?</p>