Java DP solution for beginner


  • 0

    alt text

        public int minimumTotal(List<List<Integer>> triangle) {
        	int n = triangle.size();
        	// opt[i][j] is the path sum start from one node of bottom layer to node (i,j)
        	int[][] opt = new int[n+1][n+1];
        	for(int i = n-1;i>=0;i--){
        		for(int j=0;j<=i;j++){
        			opt[i][j] = Math.min(opt[i+1][j],opt[i+1][j+1]) + triangle.get(i).get(j);
        		}
        	}
        	return opt[0][0];
        }

  • 0
    2

    You can use one dimension array opt[] instead. i is going to increase 1 anyway.


Log in to reply
 

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