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

深藏阁楼爱情的钟 2022-12-30 08:29 172阅读 0赞

### 问题 ###

给定一个三角形的数字阵列，选择一条自顶向下的路径，使得沿途的所有数字之和最小。（每一步只能移动到相邻的格子中）  
![在这里插入图片描述][20201224195544838.png]  
如上图所示的三角形阵列，其最小路径之和为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];
        }
    }

[20201224195544838.png]: /images/20221120/483f7444581e4a3e89f1708a323bc9d8.png