LeetCode120 ：三角形最小路径和

 1 class Solution { // 空间压缩 DP
 2     public int minimumTotal(List<List<Integer>> triangle) {
 3         int rows = triangle.size(); 
 4         if(rows == 0 || triangle == null) return 0;
 5         List<Integer> list = new ArrayList<>();
 6         list = triangle.get(rows-1); // 最后一个List也就是三角形的底边里面包含的元素最多
 7         int cols = list.size();
 8         int[] dp = new int[cols];
 9         list = triangle.get(0);
10         dp[0] = list.get(0); // 第一个元素
11         List<Integer> row = new ArrayList<>();
12         for(int i = 1; i < rows; i++){
13             row = triangle.get(i);
14             int size = row.size(); // 这一行里面包含的元素个数
15             int leftup = dp[0]; // 备份上一步中左上面的元素
16             for(int j = 0; j < size; j++){
17                 int temp = dp[j]; // 更新前的dp[j]将是更新后的leftup值
18                 if(j == 0){
19                     dp[j] = dp[j] + row.get(j); // 对于第一个元素的更新，其中第一个dp[j]是更新前的dp[j]
20                 } else if(j == size-1 && j != 0){ // 对本行最后一个元素更新
21                     dp[j] = leftup + row.get(j);
22                 }else{
23                     dp[j] = Math.min(leftup, dp[j]) + row.get(j);
24                 }
25                 leftup = temp;
26             }
27         }
28         int min = dp[0]; // 找到最小值
29         for(int d : dp){
30             if(d < min){
31                 min = d;
32             }
33         }
34         return min;
35     }
36 }