Jianbo Dai's

lc120.三角形最小路径和

 
  • Mar 27, 2021

题目链接

啊目测这个题是要用开辟一个二维dp数组的，但是题目要求用一维的，就是说可以优化成一维了，就和01背包那样反过来处理就行。这个算法的时间复杂度是O（N^2），空间复杂度是O（N）。

python:

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        size = len(triangle)
        dp = [0]*size
        dp[0] = triangle[0][0]
        for i in range(1, size):
            for j in range(i, -1, -1):
                if j == 0:
                    dp[j] = dp[j] + triangle[i][j]
                elif j == i:
                    dp[j] = dp[j-1] + triangle[i][j]
                else:
                    dp[j] = min(dp[j], dp[j-1]) + triangle[i][j]
        return min(dp)
Search