My 4ms DP Solution


  • 0
    B
    public int minimumTotal(List<List<Integer>> triangle) {
    	if (triangle.size()==1) {
    		return triangle.get(0).get(0);
    	}
    	int [][] dp = new int [triangle.size()][];
    	for(int i=0;i<dp.length;i++){
    		List<Integer> list = triangle.get(i);
    		dp[i] = new int[list.size()];
    	}
    	dp[0][0] = triangle.get(0).get(0);
    	int Min = Integer.MAX_VALUE;
    	for(int i=0;i<triangle.size()-1;i++){
    		List<Integer> list = triangle.get(i);
    		List<Integer> belowList = triangle.get(i+1);
    		int[] aboveDp = dp[i];
    		int[] belowDp = dp[i+1];
    		belowDp[0] =  aboveDp[0]+belowList.get(0);
    		belowDp[belowDp.length-1] =  aboveDp[belowDp.length-2]+belowList.get(belowList.size()-1);
    		for(int j=1;j<belowList.size()-1;j++){
    			belowDp[j] = Math.min(aboveDp[j-1], aboveDp[j])+belowList.get(j);
    		}
    	}
    	for(int tmp:dp[dp.length-1]){
    		if (tmp<Min) {
    			Min = tmp;
    		}
    	}
    	return Min;
    }

Log in to reply
 

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