NeetCode #674LC-120Medium1-D Dynamic Programming
← Back to All Problems#674 · #120 · Triangle(三角形最小路径和)
📌 Problem Statement & Constraints
Given a
triangle array, return the minimum path sum from the top to the bottom, where each step moves to an adjacent number in the row below. Constraints: 1 <= triangle.length <= 200, -10^4 <= triangle[i][j] <= 10^4.💡 Core Algorithmic Approaches
- Let
dp[j]be the minimum path sum reaching positionjof the current row. - Working bottom-up, position
jof rowican be reached fromjorj + 1of rowi + 1, sodp[j] = triangle[i][j] + min(dp[j], dp[j + 1]). - Starting from the bottom row and overwriting the same array in place needs no extra allocation.
- The answer is
dp[0]after processing the top row.
💻 Benchmark Python3 Implementation
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
dp = triangle[-1][:] # start from the bottom row
for i in range(len(triangle) - 2, -1, -1):
for j in range(len(triangle[i])):
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
return dp[0]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): every element of the triangle is visited once.
💾 Space Complexity
O(n): a single row of the triangle.
⚠️ Interview Pitfalls & Follow-ups
- Moving greedily to the smaller neighbour: a locally smaller value can lead to a worse total;
[[2],[3,4],[6,5,7],[4,1,8,3]]is the classic counterexample. - Indexing
dp[j + 1]out of range: the bottom-up order guarantees that entry belongs to the row below and exists. - Mutating the input triangle when it must be preserved: copy the bottom row rather than aliasing it.
- Running top-down without sentinels: not every position is reachable in every row, so top-down needs care with unreachable states.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.