# 数塔问题 ：要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
# 转移方程：sum[i] = max(a[左孩子] , a[右孩子]) + a[i]

v = [9, 12, 15, 10, 6, 8, 2, 18, 9, 5, 19, 7, 10, 4, 16]

def m(a, b):
  '''
  本程序会重复计算一些m值
  优化方法：将计算后的m存到一个字典里
  '''
  if a == 4:
    return v[b]

  L = m(a + 1, a + b + 1)
  R = m(a + 1, a + b + 2)
  if L > R:
    return L + v[b]
  else:
    return R + v[b]

if __name__ == '__main__':
  print(m(0,0))