Java DP without List#get


  • 0
    A

    I don't like the fact that a lot of the java DP solutions use List#get(index). It seems to me that those solutions assume the Lists that are passed in are ArrayLists and offer constant-time access to elements of the list. The following doesn't make that assumption and I believe is more efficient with lists that don't offer constant time access to elements with 'get'. It's not pretty though. :/

    public class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int[] lastRow = null;
            int rowIndex = 0;
            for (List<Integer> row: triangle){
                int[] thisRow = new int[triangle.size()];
                if (lastRow == null){ 
                    thisRow[0]=row.get(0);
                }
                else {
                    int col=0;
                    for (int val: row){
                        int leftParent  = (col==0) ? Integer.MAX_VALUE : lastRow[col-1];
                        int rightParent = (col==rowIndex) ? Integer.MAX_VALUE : lastRow[col];
                        thisRow[col]= Math.min(leftParent, rightParent) + val;
                        col++;
                    }
                }
                lastRow=thisRow;
                rowIndex++;
            }
            
            int min = lastRow[0];
            for (int val: lastRow){
                min = Math.min(min, val);
            }
            return min;
        }
    }
    

Log in to reply
 

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