做网站好做吗,房产网站编辑如何做,如何修改wordpress模板栏目的属性,做网站用什么后缀格式做好难度#xff1a; 中等通过率#xff1a; 37.6%题目链接#xff1a;. - 力扣#xff08;LeetCode#xff09;
题目描述
给定一个三角形#xff0c;找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如#xff0c;给定三角形#xff1a;
[[2],[3…难度 中等通过率 37.6%题目链接. - 力扣LeetCode
题目描述
给定一个三角形找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如给定三角形
[[2],[3,4],[6,5,7],[4,1,8,3]
]自顶向下的最小路径和为 11即2 3 5 1 11。
说明
如果你可以只使用 O(n) 的额外空间n 为三角形的总行数来解决这个问题那么你的算法会很加分。
解法一递归
从第一层起在某一层上希望知道顶点到该层上的最短的路径为多少。这需要在该层上计算顶点到达每个点的路径和然后取最小的。到某个点的最短路径即用该点的值加上到达该点上方两个点的最短路径。由此分析这可以写成一个递归调用。
min_path_sum 计算到达地 level 层的第 i 个点的最短路径和。首先从最后一层的每个点出发递归地调用 min_path_sum求出达到该点上一层左右两个节点的最短路径进而得到到达该点的最短路径。
class Solution {
public:int minimumTotal(vectorvectorint triangle) {int min_total INT_MAX;int level triangle.size() - 1;for(int i 0; i triangle[level].size(); i){int n min_path_sum(triangle, level, i);min_total min(min_total, n);}return min_total;}int min_path_sum(vectorvectorint triangle, int level, int i){if(level 0){return triangle[0][0];}int n1 INT_MAX, n2 INT_MAX;if(i triangle[level-1].size()){n1 min_path_sum(triangle, level-1, i);}if(i 0){n2 min_path_sum(triangle, level-1, i-1);}return min(n1, n2) triangle[level][i];}
};上面这算法是正确的但是不能性能太差因为存在大量的重复计算。可以采用备忘录避免重复计算。但是此问题还有更简洁的解法见解法二。
解法二
2
3 4
6 5 7
4 1 8 3输入的三角形可以视为一个栅栏网络遇到栅栏网络我首先想到了维特比算法。三角形的每一层都看做一个栅栏只有相邻的栅栏相互连接。如下图 图中任何一个点到起点的路径之和都可以基于前一层节点到起点的路径和计算出来。比如上图中的第二层编号为 1 的点只需要用第一层中三个点中最小值加上自身就可以了其余点也可以这么一层层地计算出来。
本题中我们可以从下往上计算因为这样可以很容易确定前一层与节点 i 相连的节点i 和 i1)。
class Solution {
public:int minimumTotal(vectorvectorint triangle) {if (triangle.size() 1) {return triangle[0][0];}for (int level triangle.size() - 2; level 0; level--) {for (int i 0; i triangle[level].size(); i) {int n min(triangle[level 1][i], triangle[level 1][i 1]);triangle[level][i] n;}}return triangle[0][0];}
};
