#
# Eksamensopgave 54
#

MAXINT = 2147483647

# Opgavens udgave

def OBV(bt, first, last):
  if first > last:
    return (0,0)
  elif first == last:
    return (bt[first], 0)
  else:
    MinVal = MAXINT
    for i in range(first, last+1):
      r = bt[i]
      (cl,vl), (cr,vr) = OBV(bt, first, i-1), OBV(bt, i+1, last)
      c, v = cl + r + cr, vl + cl + vr + cr
      if v < MinVal:
	Count, MinVal = c, v
    return (Count, MinVal)


# d)

def OBVD(bt, first, last, M):
  if first > last:
    return (0,0)
  
  elif M[first][last] == None:
    if first == last:
      M[first][last] = (bt[first], 0)
    else:
      MinVal = MAXINT
      for i in range(first, last+1):
	r = bt[i]
	(cl,vl), (cr,vr) = OBVD(bt, first, i-1, M), OBVD(bt, i+1, last, M)
	c, v = cl + r + cr, vl + cl + vr + cr
	if v < MinVal:
	  Count, MinVal = c, v
      M[first][last] = (Count, MinVal)

  return M[first][last]

def OBVdyn(bt):
  M = []
  for i in range( len(bt)):
    M.append([None] * len(bt))
  return OBVD(bt, 0, len(bt)-1, M)
	
#
# Test
#

A = [30,42,3,18,2,5]

print OBV(A, 0, len(A)-1)     # (100, 70) - tager 0.05 sek.
print OBVdyn(A)               # (100, 70) - tager 0.04 sek.

B = [30,42,3,18,2,5,30,42,3,18,2,5,30,42,3]

#print OBV(B, 0, len(B)-1)    # (275, 449) - tager 112.7  sek.
print OBVdyn(B)               # (275, 449) - tager   0.02 sek.

C = [30,42,3,18,2,5,30,42,3,18,2,5,30,42,3,18,2,5]

#print OBV(C, 0, len(C)-1)    # (300, 524) - tager mere end 25 min.
print OBVdyn(C)               # (300, 524) - tager 0.08 sek.