DP Solution for Triangle


  • 321
    S

    This problem is quite well-formed in my opinion. The triangle has a tree-like structure, which would lead people to think about traversal algorithms such as DFS. However, if you look closely, you would notice that the adjacent nodes always share a 'branch'. In other word, there are overlapping subproblems. Also, suppose x and y are 'children' of k. Once minimum paths from x and y to the bottom are known, the minimum path starting from k can be decided in O(1), that is optimal substructure. Therefore, dynamic programming would be the best solution to this problem in terms of time complexity.

    What I like about this problem even more is that the difference between 'top-down' and 'bottom-up' DP can be 'literally' pictured in the input triangle. For 'top-down' DP, starting from the node on the very top, we recursively find the minimum path sum of each node. When a path sum is calculated, we store it in an array (memoization); the next time we need to calculate the path sum of the same node, just retrieve it from the array. However, you will need a cache that is at least the same size as the input triangle itself to store the pathsum, which takes O(N^2) space. With some clever thinking, it might be possible to release some of the memory that will never be used after a particular point, but the order of the nodes being processed is not straightforwardly seen in a recursive solution, so deciding which part of the cache to discard can be a hard job.

    'Bottom-up' DP, on the other hand, is very straightforward: we start from the nodes on the bottom row; the min pathsums for these nodes are the values of the nodes themselves. From there, the min pathsum at the ith node on the kth row would be the lesser of the pathsums of its two children plus the value of itself, i.e.:

    minpath[k][i] = min( minpath[k+1][i], minpath[k+1][i+1]) + triangle[k][i];
    

    Or even better, since the row minpath[k+1] would be useless after minpath[k] is computed, we can simply set minpath as a 1D array, and iteratively update itself:

    For the kth level:
    minpath[i] = min( minpath[i], minpath[i+1]) + triangle[k][i]; 
    

    Thus, we have the following solution

    int minimumTotal(vector<vector<int> > &triangle) {
        int n = triangle.size();
        vector<int> minlen(triangle.back());
        for (int layer = n-2; layer >= 0; layer--) // For each layer
        {
            for (int i = 0; i <= layer; i++) // Check its every 'node'
            {
                // Find the lesser of its two children, and sum the current value in the triangle with it.
                minlen[i] = min(minlen[i], minlen[i+1]) + triangle[layer][i]; 
            }
        }
        return minlen[0];
    }

  • 0
    S

    I think usage of pointer will save more space and time, here's my solution using pointer.

    Run time:24 ms

    class Solution {
    public:
    int minimumTotal(vector<vector<int> > &triangle) {
    	if (triangle.size() == 0)
    		return 0;
    	if (triangle.size() == 1)
    		return triangle[0][0];
    	
    	int **pTriangle = new int*[triangle.size()];
                //initialize pointer array.
    	for (int i = 0; i < triangle.size(); i++)
    		pTriangle[i] = new int[triangle[i].size()];
                //initialize the last layer.
    	for (int i = 0; i < triangle[triangle.size() - 1].size(); i++)
    		pTriangle[triangle.size() - 1][i] = triangle[triangle.size() - 1][i];
    	//bottom up the result -  pTriangle
    	for (int i = triangle.size() - 2; i >= 0; i--)
    	{
    		for (int j = 0; j < triangle[i].size(); j++)
    		{
    			pTriangle[i][j] = min(pTriangle[i + 1][j], pTriangle[i + 1][j+1]) + triangle[i][j];
    		}
    	}
    	return pTriangle[0][0];
    }
    };

  • 0
    S

    Nice solution. Thank you for sharing!


  • 0
    S

    Hi Simon,

    Thanks for sharing, but your solution allocates O(N2) space, where N is the number of rows. This is what I avoided in my solution. Also, you need to remember to deallocate the pointers before returning to avoid memory leak.


  • 0
    T
    This post is deleted!

  • 0
    R

    Can you give some explanation of your solution? Especially for the @return phrase.


  • 5
    R

    My solution used a BFS like solution. It is also DP and O(n) complexity.

    It is written in JAVA

    public class Triangle{
    public int minimumTotal(List<List<Integer>> triangle) {
        Deque<Integer> queue = new LinkedList<Integer>();
        int count=triangle.size();
        queue.add(triangle.get(0).get(0));
        for (int i=1;i<count;i++){
            List<Integer> list= triangle.get(i);
            for (int j=0;j<=i;j++){
            	int min=0;
                if (j==0)
                	 min=list.get(0)+queue.peekFirst();               	
                else if (j==i)
                	 min =list.get(j)+queue.pollFirst();              	
                else
                	min = Math.min(queue.pollFirst(),queue.peekFirst())+list.get(j);              	               
                queue.addLast(min);               
            }
        }
        int result=Integer.MAX_VALUE;
        for (int i=0;i<count;i++)
        	result=Math.min(result, queue.pollFirst());
        return result;
    }
    

    }


  • 0
    Z

    very nice and neat,the thinking is very clear!


  • 0
    L

    great idea! thank you for your sharing!


  • 0
    C

    Cool solution! I say it is as good as bottom down dp. But yours is not easy to come up with.


  • 0
    R

    Thanks! It is my first version. Now I found the top solution is the best one.


  • 0
    L

    I think you have an error in solution that triangel is empty. minlen will be out of range.


  • 0
    L
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example.

    Thanks to @reeclapple for supporting admin.


  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 6
    H

    My DP solution. By modifying the vector,no other space is used.

    class Solution {
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
            int n= triangle.size();
            for(int i=n-2 ; i>=0 ; i--){
                for(vector<int>::size_type j=0 ; j<triangle[i].size() ; j++ ){
                    triangle[i][j] = min(triangle[i][j]+triangle[i+1][j],triangle[i][j]+triangle[i+1][j+1]);
                }
            }
            return triangle[0][0];
        }
    };

  • 0
    A

    Good explanation!


  • 0
    S

    I am using the same method in Python, but its giving me an error, time limit exceeded.!


  • 11
    X

    I have the same idea just as yours ,but that is java-version,transform"top to buttom"to "buttom to top"

    [

    [2],

    [3,4],

    [6,5,7],

    [4,1,8,3]

    ]

    is much more clear to understand

    public int minimumTotal1(List<List<Integer>> triangle) {
    	int rowNum = triangle.size();
    	int[] dp = new int[rowNum];
    	for (int i = 0; i < triangle.get(rowNum - 1).size(); i++) {
    		dp[i] = triangle.get(rowNum - 1).get(i);
    	}
    	for (int row = rowNum - 2; row >= 0; row--) {// for each layer
    		for (int col = 0; col <= row; col++) {
    			dp[col] = Math.min(dp[col], dp[col + 1])
    					+ triangle.get(row).get(col);
    		}
    	}
    	return dp[0];
    }
    
    public int minimumTotal(List<List<Integer>> triangle) {
    	int rowNum = triangle.get(triangle.size() - 1).size();
    	int colNum = triangle.size();
    	int[][] dp = new int[rowNum][colNum];
    	int i = 0;
    	for (Integer n : triangle.get(colNum - 1)) {
    		dp[rowNum - 1][i++] = n;
    	}
    	for (int row = rowNum - 2, m = 0; row >= 0; row--, m++) {
    		for (int col = 0; col <= colNum - 2 - m; col++) {
    			dp[row][col] = Math.min(dp[row + 1][col], dp[row + 1][col + 1])
    					+ triangle.get(row).get(col);
    		}
    	}
    	return dp[0][0];
    }

  • 19
    J

    A similar solution in java but without using additional memory. Just save the value in the triangle itself.

     public int minimumTotal(List<List<Integer>> triangle) {
    		if(triangle.size() == 0)
    			return 0;
    		
    		for (int i=triangle.size() - 2; i>=0; i--) {
    			for (int j=0; j<=i; j++) {
    				List<Integer> nextRow = triangle.get(i+1);
    				int sum = Math.min(nextRow.get(j), nextRow.get(j+1)) + triangle.get(i).get(j);
    				triangle.get(i).set(j, sum);
    			}
    		}
    		return triangle.get(0).get(0);
    	}
    

Log in to reply
 

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