求三角形的最短路径

ゝ一世哀愁。 2022-05-20 07:26 254阅读 0赞

![这里写图片描述][70]

import java.util.*;
    public class Solution {
    
        //(1)不考虑元素的相邻情况
        public int minimumTotal01(ArrayList<ArrayList<Integer>> triangle) {
           if(triangle==null||triangle.size()==0)
                return 0;
           int res=0;
           for(ArrayList<Integer>arr:triangle)
           {
    
               int min=Integer.MAX_VALUE;
               for(int k:arr){
    
                 min=Math.min(min,k);
               }
               res+=min;
           }
    
            return res;
        }
    
        /* // 给定一个三角形，找出从顶到底的最小路径和，每一步可以从上一行移动到下一行相邻的数字 // [ // [2], [2], // [3,4], [3, 4], [2], // [6,5,7], ==> [7, 6, 10] ==> [9, 10] ==> [11] // [4,1,8,3] // ] * / /**思路: * 自底向上 dp: 不需要额外的空间 * dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j] * dp[i][j]: 表示到达 (i, j)最小路径的总和 */
        //从下往上依次计算
       public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
           if(triangle==null||triangle.size()==0)
                return 0;
           int[]dp=new int[triangle.size()];
           ArrayList<Integer>last=triangle.get(triangle.size()-1);//最后一层的数据
           //最后一层赋给dp数组
           for(int i=0;i!=last.size();i++)
               dp[i]=last.get(i);
           //倒数第二层开始赋值
           for(int i=triangle.size()-2;i!=-1;i--)
             {
    
                ArrayList<Integer>cur=triangle.get(i);
                //每个节点和下一层的相邻的两个节点比较
                for(int j=0;j<cur.size();j++){
    
                   dp[j]=Math.min(cur.get(j)+dp[j],cur.get(j)+dp[j+1]);
                }
             }
    
              return dp[0];
        }
    
    public static  void main(String[]args){
            //System.out.println("Hello World!");
           ArrayList<Integer>arr1=new ArrayList<>();
           arr1.add(2);
    
           ArrayList<Integer>arr2=new ArrayList<>();
           arr2.add(3);
           arr2.add(4);
    
    
           ArrayList<Integer>arr3=new ArrayList<>();
           arr3.add(6);
           arr3.add(5);
           arr3.add(7);
    
    
           ArrayList<Integer>arr4=new ArrayList<>();
           arr4.add(4);
           arr4.add(1);
           arr4.add(8);
           arr4.add(3);
    
    
           ArrayList<ArrayList<Integer>> triangle=new ArrayList<>();
           triangle.add(arr1);
           triangle.add(arr2);
           triangle.add(arr3);
           triangle.add(arr4);
           Solution s=new Solution();
           System.out.println(s.minimumTotal(triangle));
    
    
        }
    }

[70]: /images/20220520/ecf868745914441a9f0e2f55f8ff2f8f.png