LeetCode-Triangle 小咪咪 2022-08-04 12:42 128阅读 0赞 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. 题比较简单，dp问题，并且要求空间复杂度了。 public int minimumTotal(List<List<Integer>> triangle) { if (triangle == null || triangle.size() == 0) return 0; int[] dp = new int[triangle.size()]; dp[0] = triangle.get(0).get(0); for (int i = 1; i < triangle.size(); i++) { List<Integer> list = triangle.get(i); dp[i] = list.get(i)+dp[i-1]; for (int j = i-1; j > 0; j--) { dp[j] = Math.min(dp[j], dp[j-1])+list.get(j); } dp[0] += list.get(0); } int min = dp[0]; for (int n : dp) { min = Math.min(min, n); } return min; }
还没有评论，来说两句吧...