My AC Code,main idea: sum[j]=min(sum[j-1],sum[j])+b[j]? min(sum[0......size]) is answer!


  • 0
    L
    public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if(triangle==null&&triangle.size()==0) return 0;
        int tmp[]=new int[triangle.size()];
        int sum;
        sum=tmp[0]=triangle.get(0).get(0);
        for(int i=1;i<triangle.size();i++){
            ArrayList<Integer> list=triangle.get(i);
            for(int j=list.size()-1;j>=0;j--){
                if(j==list.size()-1){
                    sum=tmp[j]=tmp[j-1]+list.get(j);
                }
                else if(j==0){
                    tmp[j]=tmp[j]+list.get(j);
                }
                else{
                    tmp[j]=Math.min(tmp[j-1],tmp[j])+list.get(j);
                }
                if(sum>tmp[j]){
                    sum=tmp[j];
                }
            } 
        }
        return sum;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.