Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. https://leetcode.com/problems/triangle/

minimum triangle path.py

from collections import defaultdict

class Solution:
  #top down
  def minimumTotal(self, triangle):
    if not triangle:
      return None
    minCost = [] # [ [(int,[elems)]]], [[cost1,[path2cost1]],[(cost2,[path2cost2])...
    minCost.append([(triangle[0][0], [triangle[0][0]])])  # add first level
    for rowId in range(1, len(triangle)):
      minCost.append([])
      for elemId in range(0, len(triangle[rowId])):      
        e = triangle[rowId][elemId]

        m = min(minCost[rowId-1][max(elemId-1,0):elemId+1])
        
        minlist = m[1][:]# copy to new list 
        minlist.append(e)
        newMin = (m[0] + e , minlist)
        minCost[rowId].append(newMin)
        print "DEBUG: minCost so far = " + str(minCost)
    
    print min(minCost[-1])