By

Contents
  1. 1. 题目
  2. 2. 解题思路

题目

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

使用2个数组，以最后一行为长度限制，每次上一行到下一个，下一行除了首尾，只有访问数组前一个和当前
动态规划
执行用时 :5 ms, 在所有 Java 提交中击败了64.61%的用户 内存消耗 :37.7 MB, 在所有 Java 提交中击败了60.44%的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int height = triangle.size();
        int weight = triangle.get(height-1).size();
        int[] first = new int[weight];
        int[] second = new int[weight];
        for(int i = 0 ; i < height ; i++){
            List<Integer> list = triangle.get(i);
            int size = list.size();
            for(int j = 0 ;j< size; j++){
                if(j == 0){
                    second[j] = first[j]+list.get(j);
                }else if(j == size-1){
                    second[j] = first[j-1]+list.get(j);
                }else{
                    second[j] = Math.min(first[j-1]+list.get(j),first[j]+list.get(j));
                }
            }
            int[] tmp = first;
            first = second;
            second = tmp;
        }
        int min = Integer.MAX_VALUE;
        for(int m = 0 ; m < weight ; m++){
            min = Math.min(first[m],min);
        }
        return min;
    }
}
Contents
  1. 1. 题目
  2. 2. 解题思路