三角形最小路径和

题目描述

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

数据样例

示例 1：

1
2
3
4
5
6
7
8
输入：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：

1
2
输入：triangle = [[-10]]
输出：-10

提示：

  • $1 \leq triangle.length \leq 200$
  • $triangle[0].length == 1$
  • $triangle[i].length == triangle[i - 1].length + 1$
  • $-10 ^ 4 \leq triangle[i][j] \leq 10 ^ 4$

动态规划 - $O(N ^ 2)$

动态规划

这是一道非常经典的动态规划题目

观察最小路径和对应路径（如下图中红色标记）的其中某个点

  • 对于值为 $5$ 的点，发现所有到当前节点的路径可以 分为两个部分：
    • 经过其父节点 $3$
    • 经过其父节点 $4$

因此我们可以利用这样的递推关系找到状态转移方程 （下图红框）

  • 状态表示： $f[i][j]$ 表示所有从根节点到当前节点的最小路径和
  • 状态转移：
    $$f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]$$
  • 答案：到达最后一层（$n - 1$ 层）的所有最小路径和中找到最小的
    $$\displaystyle{\underset{i \in [0, n)}{min}(f[n - 1][i])}$$

边界处理

  • 初始化
    • 由于我们要求解的是最小值，因此初始化 $f[i][j] = +\infty$
    • 初始第一个点：$f[0][0] = triangle[0][0]$
  • 状态转移
    • 第 $i$ 层（从第 $0$ 层开始记录）有 $i + 1$ 个点，因此 $j$ 枚举范围为 $[0, i]$
    • 下图左侧红框：对于 $f[i - 1][j - 1]$ 需要满足：$j > 0$，也就是每一层的第一个节点是不能通过这个转移的。
    • 下图右侧红框：对于 $f[i - 1][j]$ 需要满足：$j < i$，也就是每一层的最后一个节点是不能通过这个转移的。

时间复杂度 - $O(N ^ 2)$

  • 枚举所有的点，因此时间复杂度为：$O(N ^ 2)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func minimumTotal(triangle [][]int) int {
    n:= len(triangle)
    // 创建 f 数组
    f := make([][]int, n)
    for i := range f { f[i] = make([]int, n) }
    // 初始化 f[0][0]
    f[0][0] = triangle[0][0]
    // 从第 1 层开始，依次枚举所有节点
    for i := 1; i < n; i++ {
        for j := 0; j <= i; j++ {
            // 因为要求最小值，所以初始化为无穷大
            f[i][j] = 1e9
            // 边界情况：跳过最右侧的点
            if j < i { f[i][j] = min(f[i][j], f[i - 1][j] + triangle[i][j]) }
            // 边界情况：跳过最左侧的点
            if j > 0 { f[i][j] = min(f[i][j], f[i - 1][j - 1] + triangle[i][j] )}
        }
    }
    // 答案初始化为无穷大
    res := int(1e9)
    // 所有到达最后一层的最小路径和里找到最小的
    for i := 0; i < n; i++ { res = min(res, f[n - 1][i]) }
    return res
}

func min(a, b int) int { if a < b { return a }; return b }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> f(n, vector<int>(n, 1e9));
        f[0][0] = triangle[0][0];
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (j < i) f[i][j] = min(f[i][j], f[i - 1][j] + triangle[i][j]);
                if (j) f[i][j] = min(f[i][j], f[i - 1][j - 1] + triangle[i][j]);
            }
        }
        int res = 1e9;
        for (int i = 0; i < n; ++i) res = min(res, f[n - 1][i]);
        return res;
    }
};