三角形最小路径和

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

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

示例说明请见LeetCode官网。

来源：力扣（LeetCode）

链接：

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：动态规划

使用一个数组记录到达每一层的结点的最小的路径和，然后动态规划的过程有以下依据：

每一层的第一个结点只能由上一层的第一个结点到达；每一层的第 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));    }}

【每日寄语】 你就把现在的辛苦，看成一种投资，是对未来的投资，你以后才会有舒舒服服的自由。