給定一個三角形陣列
triangle，找出從頂部到底部的最小路徑總和。每一步只能移動到下一行的相鄰節點（即索引i或i+1）。
Example:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11
Intuition
TIP
從底部往上 DP，每個位置選擇下一行左右鄰居中較小的加上自己。
- 自頂向下會需要處理邊界，自底向上更簡潔
dp[j]代表從底部到當前行第j個位置的最小路徑和- 狀態轉移：
dp[j] = triangle[i][j] + min(dp[j], dp[j+1]) - 可以直接用一維陣列滾動更新
Approaches
1. Top-Down Memoization — O(n^2) / O(n^2)
- Idea: 從頂部遞迴向下，記憶化每個
(row, col)的最小路徑和 - Time:
O(n^2) - Space:
O(n^2)
class Solution {
fun minimumTotal(triangle: List<List<Int>>): Int {
val n = triangle.size
val memo = Array(n) { IntArray(it + 1) { Int.MAX_VALUE } }
fun dp(row: Int, col: Int): Int {
if (row == n) return 0
if (memo[row][col] != Int.MAX_VALUE) return memo[row][col]
memo[row][col] = triangle[row][col] + minOf(dp(row + 1, col), dp(row + 1, col + 1))
return memo[row][col]
}
return dp(0, 0)
}
}⭐ 2. Bottom-Up with O(n) Space — O(n^2) / O(n)
- Idea: 從最底行往上逐行合併，只用一維陣列記錄當前行的最小路徑和
- Time:
O(n^2) - Space:
O(n)
class Solution {
fun minimumTotal(triangle: List<List<Int>>): Int {
val n = triangle.size
val dp = triangle[n - 1].toIntArray()
for (i in n - 2 downTo 0) {
for (j in 0..i) {
dp[j] = triangle[i][j] + minOf(dp[j], dp[j + 1])
}
}
return dp[0]
}
}🔑 Takeaways
- Pattern: 自底向上 DP — 反向思考可以簡化邊界處理
- Key trick: 從底部往上更新時，
dp[j+1]尚未被覆蓋，因此可以安全地用一維陣列滾動