113.三角形最小路径和
题目
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
- 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
- 输出：11 解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：
- 输入：triangle = [[-10]]
- 输出：-10
思路
核心思路：从底部向上动态规划
为什么从底部向上？
如果我们从上往下走，每条路径的分支越来越多，很难直接知道哪个是最优的。但如果从底部向上走，每个位置的最小路径和只依赖于它下面一层的两个邻居，问题就变成了一个简单的递推。
状态定义
设 dp[i][j] 表示从第 i 行第 j 列出发，到达底部的最小路径和。
我们想要的就是 dp[0][0]。
状态转移
从底部倒数第二行开始，每个位置可以选择向下走左边或右边： 纯文本 dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1]) 空间优化
因为我们只需要下一行的 dp 值来计算当前行，所以可以用一个一维数组 dp 来存储当前行的计算结果，从底部向上滚动更新。
具体做法： 先将 dp 初始化为三角形最后一行（即最底层）的数字。 然后从倒数第二行开始向上遍历每一行，对于该行的每个位置 j： 纯文本 dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
这里 dp[j] 和 dp[j+1] 是下一行对应位置的值，更新后 dp[j] 就变成了当前行位置 j 的最小路径和。 最后 dp[0] 就是顶部到底部的最小路径和。
手动模拟（示例三角形）
三角形： 纯文本 2 3 4 6 5 7 4 1 8 3 初始化 dp = [4, 1, 8, 3]（最后一行）。 处理倒数第二行 [6,5,7]： dp[0] = 6 + min(4,1) = 6+1 = 7 dp[1] = 5 + min(1,8) = 5+1 = 6 dp[2] = 7 + min(8,3) = 7+3 = 10 dp 变为 [7,6,10,3]（注意最后一个3没有被覆盖，但后面不再使用）。 处理第三行 [3,4]： dp[0] = 3 + min(7,6) = 3+6 = 9 dp[1] = 4 + min(6,10) = 4+6 = 10 dp 变为 [9,10,10,3]。 处理第二行 [2]： dp[0] = 2 + min(9,10) = 2+9 = 11 dp 变为 [11,10,10,3]。 最终 dp[0] = 11 ✅
class Solution {
fun minimumTotal(triangle: List<List<Int>>): Int {
val n = triangle.size
if (n == 0) return 0
// dp 初始化为三角形的最后一行
val dp = triangle[n - 1].toMutableList()
// 从倒数第二行开始向上遍历
for (i in n - 2 downTo 0) {
// 遍历当前行的每个元素
for (j in 0..i) {
// 当前行 j 位置的最小路径和 = 当前值 + 下一行相邻两个的最小值
dp[j] = triangle[i][j] + minOf(dp[j], dp[j + 1])
}
}
// 顶部元素即为最小路径和
return dp[0]
}
}
复杂度
- 时间复杂度: O(n²)三角形有 n 行，第 i 行有 i+1 个元素，总元素数约为 n²/2，每个元素只被访问一次。
- 空间复杂度: O(n)只使用了一个长度为 n 的一维数组（最后一行长度）。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!