0120._Triangle.md

120. Triangle

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/triangle/

内容描述

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).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******

跟leetcode 931一样的思路

先是要注意下这句话：Each step you may move to adjacent numbers on the row below

在考虑adjacent number的定义，并不是角标的adjacent，而是真的形态上的adjacent

对应到角标伤的adjacent就是dp[i][j]可以由dp[i-1][j-1]和dp[i-1][j]走过来

beats 99.90%

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if not triangle or len(triangle) == 0:
            return 0

        dp = []
        for i in range(len(triangle)):
            dp.append(triangle[i])

        for i in range(1, len(triangle)):
            for j in range(i+1):
                if j == 0:
                    dp[i][j] = dp[i-1][j] + triangle[i][j]
                elif j == i:
                    dp[i][j] = dp[i-1][-1] + triangle[i][j]
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

        return min(dp[-1])

思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

空间省到O(1)

beats 99.90%

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        A = triangle
        if not A or len(A) == 0 or len(A[0]) == 0:
            return 0
            
        for i in range(1, len(A)):
            for j in range(len(A[i])):
                prev_left = A[i-1][j-1] if j-1 >= 0 else float('inf')
                prev_mid = A[i-1][j] if j < len(A[i-1]) else float('inf')
                A[i][j] += min(prev_mid, prev_left)
        return min(A[-1])