三角形最小路径和

两种解决边界问题的方案

解法一

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        rownum = len(triangle)
        dp = [[float("inf") for col in range(rownum + 1)] for row in range(rownum)]

        for row in range(rownum):
            for col in range(len(triangle[row])):
                dp[row][col + 1] = triangle[row][col]

        for row in range(1, rownum):
            for col in range(1, (len(triangle[row]) + 1)):
                dp[row][col] += min(dp[row - 1][col], dp[row - 1][col - 1])

        return min(dp[-1])

解法二
不使用额外空间

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        for row in range(1, len(triangle)):
            for col in range(len(triangle[row])):
                if col == 0:
                    triangle[row][col] += triangle[row - 1][col]
                elif (col + 1) == len(triangle[row]):
                    triangle[row][col] += triangle[row - 1][col - 1]
                else:
                    triangle[row][col] += min(triangle[row - 1][col],
                                              triangle[row - 1][col - 1])

        return min(triangle[-1])

复杂度分析

1. 时间复杂度：两种方法都是O(n^2)，n为矩阵行数
2. 空间复杂度：O(n^2)和O(0)