🌗 120. 三角形最小路径和

难度: 🌗

问题描述

---

解法

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // 思路：
        // 每行都可以求出当前行所有点处的路径和，只需要保留这一行求下一行
        // dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + [i][j]
        int height = triangle.size();
        int max = 10001;

        int[] prev = new int[height + 1]; // 获取首行
        Arrays.fill(prev, max);
        prev[0] = triangle.get(0).get(0);

        if(height == 1) {
            return prev[0];
        }
        // h > 1
        int res = max;
        // System.out.println(Arrays.toString(prev));
        for(int i = 1; i < height; i ++) {
            List<Integer> orig = triangle.get(i); // 当前行原始值
            int[] cur = new int[height + 1];
            Arrays.fill(cur, max);

            // prev 的 len == i 可以确定下来 [0, i - 1]
            for(int j = 0; j <= i; j ++) {
                int curVal = max;
                if(j - 1 >= 0 && j - 1 <= i - 1) {
                    curVal = Math.min(curVal, prev[j - 1]);
                }
                if(j >= 0 && j <= i - 1) {
                    curVal = Math.min(curVal, prev[j]); // 防止超范
                }
                curVal += orig.get(j);
                cur[j] = curVal;
                
                if(i == height - 1) {
                    res = Math.min(res, curVal);
                }
            }
            prev = cur;
            // System.out.println(Arrays.toString(cur));
        }
        return res;
    }
}

---

输出