首页 > 代码库 > Leetcode: Triangle

Leetcode: Triangle

 这道题还是挺难的一道题,想法很重要

 

 1 public class Solution {
 2     public int minimumTotal(List<List<Integer>> triangle) {
 3         int size = triangle.size();
 4         int[] leveldistances = new int[size];
 5         int[] store = new int[size];
 6         for (int i = 0; i < size; i++) {
 7             for (int j = 0; j <= i; j++) {
 8                 List<Integer> row = triangle.get(i);
 9                 if (i == 0) {
10                     leveldistances[0] = row.get(0);
11                 } 
12                 else if (j == 0) {
13                     leveldistances[j] = store[j] + row.get(j);
14                 }
15                 else if (j == i) {
16                     leveldistances[j] = store[j-1] + row.get(j);
17                 }
18                 else {
19                     leveldistances[j] = Math.min(store[j-1], store[j]) + row.get(j);
20                 }
21             }
22             store = Arrays.copyOf(leveldistances, size);
23         }
24         int minval = Integer.MAX_VALUE;
25         for (int elem : leveldistances) {
26             if (elem < minval) minval = elem;
27         }
28         return minval;
29     }
30 }