题解 | #最小三角路径和#

知识点：动态规划

思路：经典动态规划题目，最小三角形和，使用递归也可以来写，但是需要优化状态空间，这里使用动态规划来写，存储每一个子问题的最优解，

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型二维数组
     * @return int整型
     */
    public int minimumTotal (int[][] cows) {
        // write code here
        List<List<Integer>> triangle = new ArrayList<>();
        for (int[] cow : cows) {
            List<Integer> c = new ArrayList<>();
            for (int x : cow) {
                c.add(x);
            }
            triangle.add(c);
        }
        //存储最大值数组
        List<Integer> list = triangle.get(triangle.size() -1);
        list.add(10000);
        //从最底层开始
        for (int i = triangle.size() - 2; i >= 0; i--) {
            List<Integer> temp = triangle.get(i);
        //    System.out.println(temp.size());
            for (int j = 0; j < temp.size(); j++) {
                //更新list中累加的最大值，就比如i = triangle.size()-1这一层，子问题的最优解
                //不就是倒数第二层加上倒数第一层的最大值
                list.set(j, Math.min(list.get(j) + temp.get(j), list.get(j + 1) + temp.get(j)));

            //    System.out.println(list.toString());
            }
        }
        return list.get(0);
    }
}