class Solution: # @param triangle, a list of lists of integers # @return an integer # 9:11 # DP - count from bottom to top def minimumTotal(self, triangle): if not triangle: return 0 lastLevel = triangle[-1] for i in range(len(triangle) - 2, -1, -1): for j in range(i + 1): lastLevel[j] = min(lastLevel[j], lastLevel[j + 1]) + triangle[i][j] return lastLevel
I think of the similar way, but I keep adding value to the previous row instead of simply add it to the last row. Therefore, I need to further check with the boundary. Although the result is the same, yours is more simple _ Thanks for sharing!
Also share my code in the opposite direction in adding the triangle~
But still I think the original post way would be more simple :)
class Solution: # @param triangle, a list of lists of integers # @return an integer def minimumTotal(self, triangle): if not triangle: return 0 for d in range(1, len(triangle)): for idx in range(d+1): begin, end = max(0, idx-1), min(d, idx+1) triangle[d][idx] += min(triangle[d-1][begin:end]) return min(triangle[-1])