Easy to understand JAVA DP solution


  • 0
    S
    Public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int size=triangle.size();
            int [][] min=new int[size][size];//to record the min path value;
            min[0][0]=triangle.get(0).get(0);
            for(int i=0;i<size-1;i++){
                for(int j=0;j<=i+1;j++){   // top to down
                    if(j==0)min[i+1][j]=min[i][j]+triangle.get(i+1).get(j);
                    else if(j==i+1)min[i+1][j]=min[i][j-1]+triangle.get(i+1).get(j); 
                    else min[i+1][j]=Math.min(min[i][j],min[i][j-1])+triangle.get(i+1).get(j);
                }
            }
            int out=Integer.MAX_VALUE;
            for(int i=0;i<size;i++){
                if(min[size-1][i]<out)out=min[size-1][i];
            }
            return out;
        }
    }

Log in to reply
 

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