###### tags: `leetcode` `dynamic-programming`
# 120. Triangle

## my dead body

class Solution:
    def minimumTotal(self, triangle):# List[List[int]]) -> int:
        height = len(triangle)
        
        indexTreeLeafLayer = [0] 
        for _ in range(height - 1):
            indexTreeLeafLayer += [item + 1 for item in indexTreeLeafLayer]  # a special seqeunce, should have its name
        print(indexTreeLeafLayer)
        
        theSmallers = [0] * len(triangle[-1])
        print('**', theSmallers)
        
        for layerIndex in reversed(range(height)):
            triangle[layerIndex] = [a + b for a, b in zip(theSmallers, triangle[layerIndex])]
            print(triangle)
            lenOfThisLayerInTriangle = 2 ** layerIndex
            thisLayerInTriangle = triangle[layerIndex]
            print(layerIndex, "layer index")
            indexTreeThisLayer = indexTreeLeafLayer[0 :  lenOfThisLayerInTriangle]  # the upper layer is contained in the lower layer, so the last/leaf layer has all info
            
            theSmallers = [0] * (len(indexTreeThisLayer) // 2)
            for i in range(len(indexTreeThisLayer) // 2):
                # pairwise comparision
                print(i*2, i*2+1, 'index Tree This Layer')
                if thisLayerInTriangle[indexTreeThisLayer[i*2]] <= thisLayerInTriangle[indexTreeThisLayer[i*2+1]]:
                    theSmallers[i] = thisLayerInTriangle[indexTreeThisLayer[i*2]]
                else:
                    theSmallers[i] += thisLayerInTriangle[indexTreeThisLayer[i*2+1]]
                print("@@", theSmallers)

        return theSmallers[0]+ triangle[0][0]

tri = [[2],[3,4],[6,5,7],[4,1,8,3]]


print('ANS', Solution().minimumTotal(tri))
        

## me, pass

class Solution:
    def minimumTotal(self, triangle):# List[List[int]]) -> int:
        for layerIndex in range(len(triangle) - 1, 0, -1):        
            layer = triangle[layerIndex]
            aboveLayer = triangle[layerIndex - 1]
            for i in range(len(layer) - 1):
                if layer[i] <= layer[i + 1]:
                    aboveLayer[i] += layer[i]
                else:
                    aboveLayer[i] += layer[i+1]
        return triangle[0][0]
                    

### revision, pass

class Solution:
    def minimumTotal(self, triangle):# List[List[int]]) -> int:
        for layerIndex in range(len(triangle) - 1, 0, -1):        
            layer = triangle[layerIndex]
            aboveLayer = triangle[layerIndex - 1]
            for i in range(len(layer) - 1):
                aboveLayer[i] += min(layer[i], layer[i + 1]) 
        return triangle[0][0]
                    

### revision, pass

class Solution:
    def minimumTotal(self, triangle):# List[List[int]]) -> int:
        for layerIndex in range(len(triangle) - 1, 0, -1):        
            for i in range(layerIndex):
                triangle[layerIndex - 1][i] += min(triangle[layerIndex][i], triangle[layerIndex][i + 1]) 
        return triangle[0][0]