首页 > 代码库 > 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).
Solution:
public class Solution { public int minimumTotal(List<List<Integer>> triangle) { if (triangle.size()==0) return 0; if (triangle.size()==1){ List<Integer> temp = triangle.get(0); return temp.get(0); } List<Integer> pre = new ArrayList<Integer>(); List<Integer> cur = new ArrayList<Integer>(); cur.add(triangle.get(0).get(0)); for (int i=1;i<triangle.size();i++){ pre = cur; cur = new ArrayList<Integer>(); List<Integer> curTri = triangle.get(i); //j==0 cur.add(curTri.get(0)+pre.get(0)); //j==1 to (size()-2) for (int j=1;j<curTri.size()-1;j++) if (pre.get(j-1)<pre.get(j)) cur.add(curTri.get(j)+pre.get(j-1)); else cur.add(curTri.get(j)+pre.get(j)); //j==size()-1 int last = curTri.size()-1; cur.add(curTri.get(last)+pre.get(last-1)); } int min = Integer.MAX_VALUE; for (int i=0;i<cur.size();i++) if (cur.get(i)<min) min = cur.get(i); return min; }}
This is a DP problem. At each point, the min path = min(min path to its left adjacent in higher level, min path to its right adjacent in higher level)+its value.
Just be careful when addressing boundary points.
Leetcode-Triangle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。