关于java:LeetCode120三角形最小路径和

33次阅读

共计 1661 个字符，预计需要花费 5 分钟才能阅读完成。

题目形容：给定一个三角形 triangle，找出自顶向下的最小门路和。

每一步只能挪动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标雷同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于以后行的下标 i，那么下一步能够挪动到下一行的下标 i 或 i + 1。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：动静布局

应用一个数组记录达到每一层的结点的最小的门路和，而后动静布局的过程有以下根据：

每一层的第一个结点只能由上一层的第一个结点达到；

每一层的第 2 ~ size-1 个结点，能够由上一层雷同地位或者上一个地位达到，取其中的较小值；

每一层的最初一个结点只能由上一层的最初一个节点达到。

最初，返回达到最初一层结点的最小门路和。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode_120 {
    /**
     * 动静布局
     *
     * @param triangle
     * @return
     */
    public static int minimumTotal(List<List<Integer>> triangle) {
        // 记录达到每一层的每一个结点的门路和，初始化都是 0
        int[] result = new int[triangle.size()];
        for (List<Integer> integers : triangle) {
            // 记录达到以后层每一个结点的门路和，初始化都是 0
            int[] cur = new int[triangle.size()];
            // 每一层的第一个结点只能由上一层的第一个结点达到
            cur[0] = result[0] + integers.get(0);
            int index;
            for (index = 1; index < integers.size() - 1; index++) {
                // 每一层的第 2 ~ size-1 个结点，能够有上一层雷同地位或者上一个地位达到，取其中的较小值
                cur[index] = integers.get(index) + Math.min(result[index - 1], result[index]);
            }
            if (index < integers.size()) {
                // 每一层的最初一个结点只能由上一层的最初一个节点达到
                cur[index] = integers.get(index) + result[index - 1];
            }
            result = cur;
        }
        // 最初，返回达到最初一层的最小的门路和的值
        return Arrays.stream(result).min().getAsInt();
    }

    public static void main(String[] args) {List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> one = new ArrayList<>();
        one.add(2);
        triangle.add(one);

        List<Integer> two = new ArrayList<>();
        two.add(3);
        two.add(4);
        triangle.add(two);

        List<Integer> three = new ArrayList<>();
        three.add(6);
        three.add(5);
        three.add(7);
        triangle.add(three);

        List<Integer> four = new ArrayList<>();
        four.add(4);
        four.add(1);
        four.add(8);
        four.add(3);
        triangle.add(four);

        System.out.println(minimumTotal(triangle));
    }
}