首页 > 代码库 > LeetCode——Triangle
LeetCode——Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
The minimum path sum from top to bottom is 11
(i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
原题链接:https://oj.leetcode.com/problems/triangle/
题目:给定一个三角形,找出从顶部到底部的最短路径和。每一步你可以移动到下一行的邻接数字。
思路:最初的理解是:最短路径和可以看成是找出每一行中的最小值,最后求和。
public int minimumTotal1(List<List<Integer>> triangle) { int sum = 0; for (int i = 0; i < triangle.size(); i++) { int min = triangle.get(i).get(0); for (int j = 0; j < triangle.get(i).size(); j++) { if (triangle.get(i).get(j) < min) min = triangle.get(i).get(j); } sum += min; } return sum; }
提交后发现错了,要是这样也太简单了。要求的并不是每行的最小值,而应该这样理解:到达每个元素的最小路径和为到上一层与它相邻两个元素最短路径和中较小者加上该元素的值。所以,解法可以如下:
public int minimumTotal(List<List<Integer>> triangle) { for(int i = triangle.size() - 2; i >= 0; i--) { for(int j = 0; j < triangle.get(i).size(); 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); }
reference : http://www.douban.com/note/272435660/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。