[improved to 3ms]4ms Java DP solution, please give some suggestions for improvement!


  • 0
    L

    the solution has been improved to 3ms thanks to the suggestion in answer

    public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        /**
         * dp[i] denotes the sum of path to ith element on this row
         * for every element on this row, dp[i] is calculated according to the dp on previous row
        **/
        int size = triangle.size(); //pre-store the size of triangle in "size", could improve 1ms of total time
        //if no rows in triangle
        if(size==0) return 0;
        //if only one row in triangle
        if(size==1) return triangle.get(0).get(0);
        int[] dp = new int[size];
        dp[0] = triangle.get(0).get(0);
        for(int i = 1;i< size;i++){
            List<Integer> thisRow = triangle.get(i);//pre-store the list of the current row, could improve 1ms of total time
            int[] pre = dp.clone(); //handy way to copy an array with primitive type
            dp[0] = pre[0]+thisRow.get(0);
            dp[i] = pre[i-1]+thisRow.get(i);
            for(int j = 1;j<i;j++){
                dp[j] = Math.min(pre[j-1],pre[j])+thisRow.get(j);
            }
        }
        // find the minimum value in dp as the minimum path
        int min = dp[0];
        for(int i: dp){
            if(i<min) min = i;
        }
        return min;
    }
    

    }


  • 1
    C

    This is my 3ms solution:

        int SIZE=triangle.size();
    	if (SIZE == 0)
    		return 0;
    	if (triangle.size() == 1)
    		return triangle.get(0).get(0);
    	
    	int[] keep = new int[SIZE];
    	keep[0]=triangle.get(0).get(0);
    	
    	for(int i=1;i<SIZE;i++){
    		List<Integer> thisrow=triangle.get(i);
    		int[] temp = keep.clone();
    		keep[0]=temp[0]+thisrow.get(0);
    		keep[i]=temp[i-1]+thisrow.get(i);
    		for(int j=1;j<i;j++){
    			keep[j]=thisrow.get(j)+Math.min(temp[j-1], temp[j]);
    		}
    	}
    	
    	int min=keep[0];
    	for(int k:keep){
    		if(k<min) min=k;
    	}
    	return min;

Log in to reply
 

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