【LetMeFly】120.三角形最小路径和:原地动态规划(根本不需要演变来演变去)
力扣题目链接:https://leetcode.cn/problems/triangle/
给定一个三角形 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
提示:
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
|
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
|
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
|
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
|
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
|
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
|
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和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
千篇源码题解已开源