Space
Open
Interview
From Fieldwork
Scales
Archive
Bottom-Up Strategy: By starting at the bottom and moving up, we always know the minimum path sum for every node below the current one. This naturally converges to a single value at the top (dp[0]), eliminating the need to search the last row for a minimum value.
No Boundary Checks: Unlike top-down, where you have to check if you are at the left edge or right edge of the triangle, the bottom-up approach guarantees that every node i always has children at i and i+1.
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# Initialize dp array with the values of the bottom row
dp = triangle[-1][:]
# Iterate from the second-to-last row up to the top row
for r in range(len(triangle) - 2, -1, -1):
for c in range(len(triangle[r])):
# The minimum path sum at this specific node is:
# its own value + the minimum of the two nodes below it
dp[c] = triangle[r][c] + min(dp[c], dp[c + 1])
# The top element now contains the minimum path sum for the whole triangle
return dp[0]If we are allowed to modify the input array, we can treat the input triangle as our DP table:
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
for r in range(len(triangle) - 2, -1, -1):
for c in range(len(triangle[r])):
triangle[r][c] += min(triangle[r+1][c], triangle[r+1][c+1])
return triangle[0][0]Practice bench
Drafts stay on this device.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode