120.三角形最小路径和:原地动态规划(根本不需要演变来演变去)

【LetMeFly】120.三角形最小路径和:原地动态规划(根本不需要演变来演变去)

力扣题目链接:https://leetcode.cn/problems/triangle/

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

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

 

提示:

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -104 <= triangle[i][j] <= 104

 

进阶:

  • 你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题吗?

方法一:原地修改

第$i$行的第$j$个元素可由第$i-1$行的第$j-1$ or 第$j$个元素走来。

那么具体由哪个走来呢?当然取决于上一行第$j-1$ 和 第$j$个的最小的那个。

直接在原三角形上进行修改即可。

  • 时间复杂度$O(N^2)$,其中$N$为三角形的边长
  • 空间复杂度$O(1)$

AC代码

C++

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
/*
* @Author: LetMeFly
* @Date: 2022-07-18 16:16:49
* @LastEditors: LetMeFly
* @LastEditTime: 2022-07-18 16:22:44
*/
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
for (int i = 1; i < n; i++) {
triangle[i][0] += triangle[i - 1][0];
for (int j = 1; j < i; j++) {
triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
}
triangle[i][i] += triangle[i - 1][i - 1];
}
// 返回最后一行的最小元素
int ans = triangle[n - 1][0];
for (int i = 1; i < n; i++) {
ans = min(ans, triangle[n - 1][i]);
}
return ans;
}
};
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
27
28
/*
* @Author: LetMeFly
* @Date: 2025-09-25 23:12:43
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-09-25 23:18:09
*/
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
for (int i = 1; i < triangle.size(); i++) {
for (int j = 0; j <= i; j++) {
int toAdd = 100000;
if (j - 1 >= 0) {
toAdd = min(toAdd, triangle[i - 1][j - 1]);
}
if (j < i) {
toAdd = min(toAdd, triangle[i - 1][j]);
}
triangle[i][j] += toAdd;
}
}
int ans = 100000;
for (int t : triangle.back()) {
ans = min(ans, t);
}
return ans;
}
};

方法二:原地修改(倒序遍历)

其实只需要倒着写,代码实现就会简单很多。

  • 时间复杂度$O(N^2)$,其中$N$为三角形的边长
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
* @Author: LetMeFly
* @Date: 2025-09-25 23:20:10
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-09-25 23:21:43
*/
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
for (int i = triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
}
}
return triangle[0][0];
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
Author: LetMeFly
Date: 2025-08-01 23:51:32
LastEditors: LetMeFly.xyz
LastEditTime: 2025-08-02 00:01:53
'''
from typing import List

class Solution:
def generate(self, numRows: int) -> List[List[int]]:
ans = [[1] for _ in range(numRows)]
for i in range(1, numRows):
for j in range(1, i):
ans[i].append(ans[i - 1][j - 1] + ans[i - 1][j])
ans[i].append(1)
return ans

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
* @Author: LetMeFly
* @Date: 2025-09-25 23:12:43
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-09-25 23:31:13
*/
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
for (int i = triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
}
}
return triangle.get(0).get(0);
}
}

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
* @Author: LetMeFly
* @Date: 2025-09-25 23:12:43
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-09-25 23:26:32
*/
package main

func minimumTotal(triangle [][]int) int {
for i := len(triangle) - 2; i >= 0; i-- {
for j := 0; j <= i; j++ {
triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])
}
}
return triangle[0][0]
}

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
* @Author: LetMeFly
* @Date: 2025-09-25 23:12:43
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-09-25 23:34:54
*/
impl Solution {
pub fn minimum_total(mut triangle: Vec<Vec<i32>>) -> i32 {
for i in (0..triangle.len()-1).rev() {
for j in 0..=i {
triangle[i][j] += triangle[i+1][j].min(triangle[i+1][j+1]);
}
}
return triangle[0][0];
}
}

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源


120.三角形最小路径和:原地动态规划(根本不需要演变来演变去)
https://blog.letmefly.xyz/2022/07/18/LeetCode 0120.三角形最小路径和/
作者
发布于
2022年7月18日
许可协议