首页 > 代码库 > Triangle LeetCode |My solution
Triangle LeetCode |My solution
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).
public class Solution { public int minimumTotal(List<List<Integer>> triangle) { if (triangle == null) { return 0; } int rowNumber = triangle.size() ; int [][] minArray = new int [rowNumber][rowNumber]; minArray[0][0] = triangle.get(0).get(0); for (int i = 1; i < rowNumber; i++) { for (int j = 0; j <= i ; j++) { if (j == 0) { minArray[i][j] = minArray[i-1][j] + triangle.get(i).get(j) ; } else if (j == i && j != 0) { minArray[i][j] = minArray[i-1][j - 1] + triangle.get(i).get(j); } else { minArray[i][j] = Math.min(minArray[i- 1][j] + triangle.get(i).get(j), minArray[i- 1][j - 1] + triangle.get(i).get(j)); } } } int min = minArray[rowNumber - 1][0]; for (int i = 0; i < rowNumber; i++) { if (min > minArray[rowNumber - 1][i]) { min = minArray[rowNumber - 1][i]; } } return min; }}
Triangle LeetCode |My solution
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。