题解 | #三角形#

import java.util.*;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        /*//方法一：从上往下走，最后累积的值存在了triangle.get(size-1).get(j)对应的数组arr[size-1][j]中
        int size=triangle.size(); //定义行
        //三角形的列随着行变换
        if(triangle.isEmpty()||size==0){
            return 0;
        }
        int [][] everysum=new int[size][size];
        everysum[0][0]=triangle.get(0).get(0);
        for(int i=1;i<size;i++){
            for(int j=0;j<=i;j++){
                //累计往下加
                if(j==0){
                    //最左边一行的情况
                    everysum[i][j]=triangle.get(i).get(j)+everysum[i-1][j];
                }else if(j==i){
                    //最右边一行的情况
                    everysum[i][j]=triangle.get(i).get(j)+everysum[i-1][j-1];
                }else{
                    //非边界，即0<j<i
                    everysum[i][j]=triangle.get(i).get(j)+Math.min(everysum[i-1][j],everysum[i-1][j-1]);
                }
            }
        }
        //到这一步已经累计到最后一行了，最后一行所有元素中找最小的即可
        int minsum=everysum[size-1][0];
        for(int j=1;j<size;j++){
           minsum=Math.min(minsum,everysum[size-1][j]);
        }
        
        return minsum;*/
        //方法二：从下往上走，最后累积的值存在了triangle.get(0).get(0)对应的数组arr[0][0]中
        int size=triangle.size();//==行数==最大列数
        if(size==0||triangle.isEmpty()){
            return 0;
        }
        //新建二维数组，并且把最后一行赋值上
        int[][] array=new int[size][size];
        for(int j=0;j<size;j++){
            array[size-1][j]=triangle.get(size-1).get(j);
        }
        for(int i=size-2;i>=0;i--){
            for(int j=0;j<=i;j++){
                array[i][j]=Math.min(array[i+1][j],array[i+1][j+1])+triangle.get(i).get(j);
            }
        }
        return array[0][0];
    }
}