Accepted DP Solution : O(n) space and O(n) time


  • 0
    P

    public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
    int m = triangle.size();
    int n = m*(m+1)/2;

        if(n==1) return triangle.get(0).get(0);
        
        int[] sum = new int[n];
        
        for(int i=m;i>=1;i--)
        {
            List<Integer> parent = triangle.get(i-1);
            int count = parent.size();
            int start = (count*(count-1))/2;
            if(i==m)
            {
                for(int lst=0;lst<parent.size();lst++)
                    sum[start++]=parent.get(lst);
            }
            else {
                int child_start = (count*(count+1))/2;
                for(int lst=0;lst<parent.size();lst++)
                {
                    int left=Integer.MAX_VALUE,right=Integer.MAX_VALUE;
                    left = sum[child_start];
                    right = sum[child_start+1];
                    sum[start++]=parent.get(lst)+Integer.min(left,right);
                    child_start++;
                }
            }
        }
        return sum[0];
    }
    

    }

    Since the list sizes are in order 1,2,3,4.. Total number of element n = list_length*(list_length)/2
    Created an array of n elements containing sum. Similar to minimum path in a tree, start from bottom level values as base case for DP. For every level up, the first element of that level is minimum of the first and second element of the child level (since every element can be adjacent to just these 2 elements)


Log in to reply
 

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