120. 三角形最小路径和
题目描述
输入一个三角形数组 triangle，第 i 行（从 0 开始）有 i + 1 个整数。
从顶端出发，每次走到下一行，直到最后一行。若当前位于某行下标 j 处，下一步只能去下一行的下标 j 或 j + 1。
路径和是经过的所有数之和。返回所有可能路径中最小的路径和。
示例 1
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11
解释：沿 2 -> 3 -> 5 -> 1 走，和为 11，是最小值。
示例 2
输入：triangle = [[-10]] 输出：-10
解释：只有一个数，路径和就是 -10。
数据范围
1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-10^4 <= triangle[i][j] <= 10^4
进阶：能否只用 O(n) 的额外空间完成，其中 n 是三角形的行数？
解题思路：自底向上一维 DP
自底向上。设 dp[j] 为从当前行第 j 个往下走到底的最小和，初始为最后一行。从倒数第二行向上：dp[j] = triangle[i][j] + min(dp[j], dp[j+1])。最后 dp[0] 就是从顶端出发的答案。
为什么正确
处理完第 i 行后，dp[0..i] 是第 i 行各位置到底部的最小和。
复杂度分析
时间 O(n²)，额外空间 O(n)。
易错点
自顶向下需要处理每行两端的边界，最后还要在整行中取最小值；自底向上没有这些边界问题。贪心地每步选较小的子节点是错的。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
dp = triangle[-1][:]
for i in range(len(triangle) - 2, -1, -1):
for j in range(i + 1):
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
return dp[0]class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new int[n];
for (int j = 0; j < n; j++) dp[j] = triangle.get(n - 1).get(j);
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
}
}
return dp[0];
}
}class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
vector<int> dp = triangle.back();
for (int i = (int)triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
}
}
return dp[0];
}
};func minimumTotal(triangle [][]int) int {
n := len(triangle)
dp := append([]int{}, triangle[n-1]...)
for i := n - 2; i >= 0; i-- {
for j := 0; j <= i; j++ {
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
}
}
return dp[0]
}var minimumTotal = function(triangle) {
const dp = triangle[triangle.length - 1].slice();
for (let i = triangle.length - 2; i >= 0; i--) {
for (let j = 0; j <= i; j++) {
dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
}
}
return dp[0];
};function minimumTotal(triangle: number[][]): number {
const dp = triangle[triangle.length - 1].slice();
for (let i = triangle.length - 2; i >= 0; i--) {
for (let j = 0; j <= i; j++) {
dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
}
}
return dp[0];
}其他解法
两者状态定义相同；记忆化搜索是自顶向下的写法，主解法按行自底向上迭代，并把空间压到 O(n)。
解法 2：记忆化搜索 时间 O(n²)，空间 O(n²)
dfs(i, j) 表示从第 i 行第 j 个数出发走到底部的最小路径和。最后一行直接返回自身；否则等于 triangle[i][j] 加上 dfs(i+1, j) 和 dfs(i+1, j+1) 的较小值。用二维表缓存结果，每个状态只算一次。
直接由递归定义得到，最容易想到。缓存表占 O(n²) 空间，还有递归开销；不加缓存会退化成 O(2ⁿ)。
from typing import List
from functools import lru_cache
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
@lru_cache(maxsize=None)
def dfs(i, j):
if i == n - 1:
return triangle[i][j]
return triangle[i][j] + min(dfs(i + 1, j), dfs(i + 1, j + 1))
return dfs(0, 0)class Solution {
private Integer[][] memo;
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
memo = new Integer[n][n];
return dfs(triangle, 0, 0);
}
private int dfs(List<List<Integer>> triangle, int i, int j) {
if (i == triangle.size() - 1) return triangle.get(i).get(j);
if (memo[i][j] != null) return memo[i][j];
int res = triangle.get(i).get(j) + Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1));
memo[i][j] = res;
return res;
}
}class Solution {
vector<vector<int>> memo;
vector<vector<bool>> seen;
int dfs(vector<vector<int>>& triangle, int i, int j) {
if (i == (int)triangle.size() - 1) return triangle[i][j];
if (seen[i][j]) return memo[i][j];
seen[i][j] = true;
memo[i][j] = triangle[i][j] + min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1));
return memo[i][j];
}
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
memo.assign(n, vector<int>(n, 0));
seen.assign(n, vector<bool>(n, false));
return dfs(triangle, 0, 0);
}
};func minimumTotal(triangle [][]int) int {
n := len(triangle)
memo := make([][]int, n)
seen := make([][]bool, n)
for i := range memo {
memo[i] = make([]int, n)
seen[i] = make([]bool, n)
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i == n-1 {
return triangle[i][j]
}
if seen[i][j] {
return memo[i][j]
}
seen[i][j] = true
memo[i][j] = triangle[i][j] + min(dfs(i+1, j), dfs(i+1, j+1))
return memo[i][j]
}
return dfs(0, 0)
}var minimumTotal = function(triangle) {
const n = triangle.length;
const memo = Array.from({ length: n }, () => new Array(n).fill(undefined));
const dfs = (i, j) => {
if (i === n - 1) return triangle[i][j];
if (memo[i][j] !== undefined) return memo[i][j];
memo[i][j] = triangle[i][j] + Math.min(dfs(i + 1, j), dfs(i + 1, j + 1));
return memo[i][j];
};
return dfs(0, 0);
};function minimumTotal(triangle: number[][]): number {
const n = triangle.length;
const memo: (number | undefined)[][] = Array.from({ length: n }, () => new Array(n).fill(undefined));
const dfs = (i: number, j: number): number => {
if (i === n - 1) return triangle[i][j];
const cached = memo[i][j];
if (cached !== undefined) return cached;
const res = triangle[i][j] + Math.min(dfs(i + 1, j), dfs(i + 1, j + 1));
memo[i][j] = res;
return res;
};
return dfs(0, 0);
}