首页 > 代码库 > 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