moonlightshadow123
6/23/2017 - 7:46 AM

120. Triangle

  1. Triangle
solution.py
content_copyfile_download
class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if len(triangle) == 1:
            return triangle[0][0]
        for row in range(len(triangle)-2,-1,-1):
            for col in range(len(triangle[row])):
                triangle[row][col] += min(triangle[row+1][col], triangle[row+1][col+1])
        return triangle[0][0]
120-Triangle.md
content_copyfile_download
  • Rendered
  • Source

https://leetcode.com/problems/triangle/#/description

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

For example, given the following triangle

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

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).