LeetCode 120: Triangle ·

基本資料
#

難易度: medium 第一次嘗試：2026-06-27 來源：Day 30 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

explain LC 120 as in-place DP with exact state meaning after overwrite
walk the edge cases for LC 120 left edge, right edge, and middle cells

當天筆記摘錄
#

Problem 2 - LC 120 Triangle
#

Pattern: DP on jagged rows / in-place bottom-up accumulation.

Why This Fits
#

Each position in row r depends only on legal parents from row r - 1.

The row shape is not rectangular, but the dependency is still local and acyclic, so DP fits cleanly.

Core State / Invariant
#

For the in-place version:

triangle[r][c] = minimum path sum to reach position (r, c) after update

Edge Rules
#

Left edge:

c == 0

Can only come from:

triangle[r - 1][0]

Right edge:

c == r

Can only come from:

triangle[r - 1][c - 1]

Middle cells:

triangle[r][c] += min(triangle[r - 1][c - 1], triangle[r - 1][c])

Final Answer
#

After all updates:

answer = min(triangle[last_row])

Because any position in the last row can be the endpoint of a valid top-to-bottom path.

Complexity
#

Time: O(total cells)
Space: O(1) extra

For n rows:

Time: O(n^2)

Common Mistakes
#

thinking in-place update means it is not DP
forgetting the left and right edges each have only one legal parent
saying every cell has two parents
giving vague complexity like O(n * m) when the structure is a triangle, not a rectangle

Strong Spoken Explanation
#

I update the triangle in place so that each entry becomes the minimum path sum to reach that position. The left edge has only one parent directly above, the right edge has only one parent above-left, and middle cells can come from either of the two parents in the previous row. After processing all rows, the minimum answer is the minimum value in the last row.

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = triangle[-1][:]

        for r in range(len(triangle) - 2, -1, -1):
            for c in range(len(triangle[r])):
                dp[c] = triangle[r][c] + min(dp[c], dp[c + 1])

        return dp[0]