动态规划之Triangle(三角形) Java实现

问题

给定一个三角形的数字阵列，选择一条自顶向下的路径，使得沿途的所有数字之和最小。（每一步只能移动到相邻的格子中）

如上图所示的三角形阵列，其最小路径之和为11(2+3+5+1)。

问题分析

我们对该三角形阵列从最底层求起，用一个result数组存放每一层的数的较小值和其相邻的上面一层的数之和，直到遍历到顶层，返回result[0]。
以本题为例：
1、我们先新建一个result数组，其里面的值都是0，0的较小值还是0，然后遍历其相邻的上面一层的数并求之和，得到result数组中的值为[0+4,0+1,0+8,0+3],即[4,1,8,3]。
2、同理，遍历[4,1,8,3]的较小值和遍历[4,1,8,3]的相邻的上一层的数[6,5,7]之和，得到result数组中的值为[1+6,1+5,3+7],即[7,6,10]。
3、同理，遍历[7,6,10]的较小值和遍历[7,6,10]的相邻的上一层的数[3,4]之和，得到result数组中的值为[6+3,6+4],即[9,10]。
4、同理，遍历[9,10]的较小值和遍历[9,10]的相邻的上一层的数[2]之和，得到result数组中的值为[9+2],即[11]。
5、返回result[0],即11。

java代码实现

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

/**
 * @author mazhen
 * @className Triangle
 * @Description TODO
 * @date 2020/12/29 16:07
 */
public class Triangle {
    public static void main(String[] args) {
        List<Integer> inList1 = new ArrayList<>();
        inList1.add(2);
        List<Integer> inList2 = new ArrayList<>();
        inList2.add(3);
        inList2.add(4);
        List<Integer> inList3 = new ArrayList<>();
        inList3.add(6);
        inList3.add(5);
        inList3.add(7);
        List<Integer> inList4 = new ArrayList<>();
        inList4.add(4);
        inList4.add(1);
        inList4.add(8);
        inList4.add(3);
        List<List<Integer>> outList = new ArrayList<>();
        outList.add(inList1);
        outList.add(inList2);
        outList.add(inList3);
        outList.add(inList4);
        System.out.println(minTriangle(outList));
    }

    public static int minTriangle(List<List<Integer>> list) {
        if (null == list)
            return 0;
        int outListSize = list.size();
        if (outListSize == 0)
            return 0;
        if (outListSize == 1)
            return list.get(0).get(0);
        //用于存放相加后的结果
        int[] result = new int[list.size()+1];
        //外层list从后往前遍历
        for (int j=outListSize-1;j>=0;j--) {
            //获取内层list
            List<Integer> inList = list.get(j);
            int inSize = inList.size();
            for (int i=0;i<inSize;i++) {
                //取result中的最小值与内部list中的值相加后写入到result数组中
                result[i] = Math.min(result[i],result[i+1]) + inList.get(i);
            }
        }
        return result[0];
    }
}

本文地址：https://blog.csdn.net/mameng1988/article/details/111651778