⚡Flashcard Drill➔
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

  1. Let dp[j] be the minimum path sum reaching position j of the current row.
  2. Working bottom-up, position j of row i can be reached from j or j + 1 of row i + 1, so dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]).
  3. Starting from the bottom row and overwriting the same array in place needs no extra allocation.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems