DP Solution for Triangle including clear explanation and picture representation


  • 0
    R

    This problem is a very good implementation of DP and can be solved using only O(n) extra space. But it is quite difficult to imagine or visualize the solution to this problem. Even if one finds the code, it will be difficult to understand the code and why they are doing it, the way they are doing it. So I am trying to explain the thought process behind the backward, DP solution.

    Lets take the triangle given in the example.

    [2],
    [3,4],
    [6,5,7],
    [4,1,8,3]

    To find the Minimum Path sum, we can visualize the above triangle in this format.

                                  2
                                /   \
                               3     4
                              /  \  /  \
                             6     5    7
                            / \   / \  / \
                           4    1     8   3
    

    Now once we visualize the triangle as the tree above, we can start processing it to find the min sum path.

    6 in row 3 can reach the row number 4 either through 4 or 1, and it will be minimum if it chooses 1, similarly 5 in row number 3 can reach row number 4 either through 1 or 8. Since we want minimum, we choose 1 and finally 7 in row number 3 can reach row number 4 either through 8 or 3. Since we want minimum we choose 3.

    So after first iteration, our result array would be 7,6,10,3. ( please see the code to understand what is result array).

    Code:

            int[] result = new int[triangle.size()];
            for(int i=0;i < currentList.size(); i++){
                result[i] = currentList.get(i);
            }
            
            for(int i=triangle.size()-2; i >=0 ;i--){
                currentList = triangle.get(i);
                
                for(int j=0;j < currentList.size();j++){
                    result[j] = Math.min(result[j], result[j+1]) + currentList.get(j);
                }
            }
     
           return result[0];
    
    

    Please comment if you have any questions.


Log in to reply
 

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