三角形最小路径和（ LeetCode 120 ）
一、题目描述
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 三角形最小路径和（ LeetCode 120 ）：https://leetcode-cn.com/problems/triangle/
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
// triangle 是个二维数组
// 先获取 triangle 的层数，即一维数组的个数
int n = triangle.size();
// 设置一个一维数组，动态的更新每一层中当前节点对应的最短路径
int[] dp = new int[ n + 1 ];
// 从最后一层开始计算节点的最短路径，直到顶层 0 层为止
for (int i = n - 1 ; i >= 0 ; i-- ){
// dp 中存储的是前 i 个位置存储的是到达第 i 层各个节点的最小路径和
// 从每一层的第 0 个位置开始
for(int j = 0 ; j <= i ; j++){
// dp[j] 表示第 i 层中第 j 个节点的最小路径和
dp[j] = triangle.get(i).get(j) + Math.min(dp[j],dp[j+1]);
}
}
// 返回结果
return dp[0];
}
}
2、C++ 代码
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
// triangle 是个二维数组
// 先获取 triangle 的层数，即一维数组的个数
int n = triangle.size();
// 设置一个一维数组，动态的更新每一层中当前节点对应的最短路径
vector<int> dp( n + 1 );
// 从最后一层开始计算节点的最短路径，直到顶层 0 层为止
for (int i = n - 1 ; i >= 0 ; i-- ){
// dp 中存储的是前 i 个位置存储的是到达第 i 层各个节点的最小路径和
// 从每一层的第 0 个位置开始
for(int j = 0 ; j <= i ; j++){
// dp[j] 表示第 i 层中第 j 个节点的最小路径和
dp[j] = triangle[i][j] + min(dp[j],dp[j+1]);
}
}
// 返回结果
return dp[0];
}
};
3、Python 代码
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# triangle 是个二维数组
# 先获取 triangle 的层数，即一维数组的个数
n = len(triangle)
# 设置一个一维数组，动态的更新每一层中当前节点对应的最短路径
dp = [ 0 for _ in range( n + 1 )]
# 从最后一层开始计算节点的最短路径，直到顶层 0 层为止
for i in range( n - 1 , -1 , -1) :
# dp 中存储的是前 i 个位置存储的是到达第 i 层各个节点的最小路径和
# 从每一层的第 0 个位置开始
for j in range( 0 , i + 1 ) :
# dp[j] 表示第 i 层中第 j 个节点的最小路径和
dp[j] = triangle[i][j] + min(dp[j],dp[j+1])
# 返回结果
return dp[0]
四、动画理解（没有声音）
隐藏内容
此处内容需要权限查看
