[DP/BackTracking]120. Triangle

• 分类：DP/BackTracking
• 时间复杂度: O(n^2)
• 空间复杂度: O(1)

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

代码：

DP代码：

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        
        #判定边界条件
        if not triangle:
            return -1
        if len(triangle)==1:
            return triangle[0][0]
        
        for i in range(1,len(triangle)):
            for j in range(len(triangle[i])):
                if j==0:
                    triangle[i][j]+=triangle[i-1][j]
                elif j==len(triangle[i])-1:
                    triangle[i][j]+=triangle[i-1][j-1]
                else:
                    triangle[i][j]+=min(triangle[i-1][j],triangle[i-1][j-1])
                    
        smallest=triangle[len(triangle)-1][0]        
        for j in range(1,len(triangle[i])):
            smallest=min(smallest,triangle[len(triangle)-1][j])
                    
        return smallest

BackTracking代码：

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        
        #判定边界条件
        if not triangle:
            return -1
        
        res=self.helper(triangle,len(triangle))

        #求最小值
        smallest=res[0]
        for j in range(1,len(res)):
            smallest=min(smallest,res[j])
                    
        return smallest
    
    def helper(self,triangle,level):
        #定义出口
        if level==1:
            return triangle[0]
        
        prev=self.helper(triangle,level-1)

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

        return triangle[level-1]

讨论：

1.经典动态规划，我竟然能自己写出来，感激涕零！！！
2.DP的题目都可以用BackTracking做！
3.注意边界，注意bug free！！！