Leetcode 120 - Triangle


Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
https://www.cnblogs.com/struggleli/p/6934287.html

X. Bottom up
https://leetcode.com/problems/triangle/discuss/38724/7-lines-neat-Java-Solution
public int minimumTotal(List<List<Integer>> triangle) {
    int[] A = new int[triangle.size()+1];
    for(int i=triangle.size()-1;i>=0;i--){
        for(int j=0;j<triangle.get(i).size();j++){
            A[j] = Math.min(A[j],A[j+1])+triangle.get(i).get(j);
        }
    }
    return A[0];
}
https://leetcode.com/discuss/5337/dp-solution-for-triangle
DP:

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 areoverlapping 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 isoptimal 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]; 

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];
}
O(1) space:
modifying input makes it thread unsafe. You'd better keep that until interviewer ask for it,
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);
    }
public int minimumTotal(List<List<Integer>> triangle) { if (triangle.size() == 0) return 0; if (triangle.size() == 1) return triangle.get(0).get(0); int[] dp = new int[triangle.size()]; dp[0] = triangle.get(0).get(0); return minimumTotal(triangle, dp, 1); } public int minimumTotal(List<List<Integer>> triangle, int[] dp, int lvlidx) { /** * dp: dp[i]_lvlidx = the min path sum up to current level and up to * index i * * dp[0]_lvlidx = this_level_list[0] + dp[0]_(lvlidx-1); * dp[end]_lvlidx = this_level_list[end] + dp[end-1]_(lvlidx-1); * * dp[i]_lvlidx = this_level_list[i] + min{ dp[i-1]_(lvlidx-1), * dp[i]_(lvlidx-1) }; */ List<Integer> list = triangle.get(lvlidx); int pre = dp[0], temp; dp[0] += list.get(0); for (int i = 1; i < lvlidx; i++) { temp = dp[i]; dp[i] = list.get(i) + Math.min(pre, dp[i]); pre = temp; } dp[lvlidx] = pre + list.get(lvlidx); if (lvlidx + 1 == triangle.size()) { int res = dp[0]; for (int i = 1; i <= lvlidx; i++) res = Math.min(res, dp[i]); return res; } return minimumTotal(triangle, dp, lvlidx + 1); }

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for(int i = triangle.size() - 2; i >= 0; i--)
            for(int j = 0; j <= i; j++)
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
        return triangle.get(0).get(0);
    }
}
The idea is simple.
1) Go from bottom to top.
2) We start form the row above the bottom row [size()-2].
3) Each number add the smaller number of two numbers that below it.
4) And finally we get to the top we the smallest sum.
What if the List is LinkedList? What is the complexity of the get function ?
it's O(n), if it's linked list, I think we should better use iterator to traverse every layer, otherwise using get/set the time complexity would be terrible




Top Down - BFS, DP
http://yucoding.blogspot.com/2013/04/leetcode-question-112-triangle.html
    int minimumTotal(vector<vector<int> > &triangle) {
        int n = triangle.size();
        if (n==0){return 0;}
         
        for (int i=1;i<n;i++){
            for (int j=0;j<triangle[i].size();j++){
                if (j==0){triangle[i][j] += triangle[i-1][j];}
                if (j>0){
                    if (i>j){
                        triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j]);
                    }else{
                        triangle[i][j] += triangle[i-1][j-1];
                    }
                     
                }
                 
            }
        }
        sort(triangle[n-1].begin(),triangle[n-1].end()); //get min
        return triangle[n-1][0];   
    }

https://leetcode.com/discuss/51099/java-top-down-dp-solution-no-extra-space
public int minimumTotal(List<List<Integer>> triangle) { List<Integer> prev = triangle.get(0); int min = prev.get(0); for (int i = 1; i < triangle.size(); i++) { List<Integer> cur = triangle.get(i); min = Integer.MAX_VALUE; for(int j = 0; j < cur.size(); j++) { int minSum = cur.get(j) + getPreviousMin(j, prev); cur.set(j,minSum); if(minSum < min) min = minSum; } prev = cur; } return min; } private int getPreviousMin(int j, List<Integer> prev) { int m1 = (j>=prev.size())?Integer.MAX_VALUE : prev.get(j); int m2 = (j<=0)? Integer.MAX_VALUE : prev.get(j-1); return Math.min(m1, m2); }
public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(), value1, value2; for(int i = 1; i < n; i++){ for(int j = 0; j <= i; j++){ if(j == 0){ value1 = triangle.get(i - 1).get(0); }else{ value1 = j == i ? triangle.get(i - 1).get(j - 1) : Math.min(triangle.get(i - 1).get(j - 1), triangle.get(i - 1).get(j)); } value2 = triangle.get(i).get(j); triangle.get(i).set(j, value1 + value2); } } int min = Integer.MAX_VALUE; for(int k = 0; k < n; k++){ // we can keep track of min in the above for-for loop min = Math.min(min, triangle.get(n - 1).get(k)); } return min; }
Solution - DFS, Recursion
This algorithm actually expand the triangle into a full binary tree and check each node constant times. For example, the example triangle becomes
[
         [2],
     [3   ,   4],
   [6 , 5   5 , 7],
  [4,1 1,8 1,8 8,3]
]
Given a triangle of n rows, the resulted binary tree will have O(2^n) nodes. Thus, it takes O(2^n) time, where n is the total number of rows, and O(n) spaces for DFS.
Since numbers could be negative, we cannot prune sub-triangle when the current sum is no less than current minimum sum.
private int DFS(ArrayList<ArrayList<Integer>> triangle, int row, int column, int sum, int minSum) {  
   // add itself  
   sum += triangle.get(row).get(column);  
   
   if (row == triangle.size() - 1) { // last row  
     if (sum < minSum) return sum;  
   } else {  
     minSum = DFS(triangle, row+1, column, sum, minSum);  
     minSum = DFS(triangle, row+1, column+1, sum, minSum);  
   }  
   
   return minSum;  
 }  
   
 public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {  
   return DFS(triangle, 0, 0, 0, Integer.MAX_VALUE);  
 }
http://www.cnblogs.com/yuzhangcmu/p/4147764.html
使用DFS 加记忆矩阵的解法.
 4     public int minimumTotal1(List<List<Integer>> triangle) {
 5         if (triangle == null || triangle.size() == 0) {
 6             return 0;
 7         }
 9         int rows = triangle.size();
10         int[][] mem = new int[rows][rows];
11         for (int i = 0; i < rows; i++) {
12             for (int j = 0; j < rows; j++) {
13                 mem[i][j] = Integer.MAX_VALUE;
14             }
15         }
17         return dfs(triangle, 0, 0, mem);
18     }
19     
20     public int dfs(List<List<Integer>> triangle, int row, int col, int[][] mem) {
21         if (mem[row][col] != Integer.MAX_VALUE) {
22             return mem[row][col];
23         }
24         
25         if (row == triangle.size() - 1) {
26             mem[row][col] = triangle.get(row).get(col);
27         } else {
28             int left = dfs(triangle, row + 1, col, mem);
29             int right = dfs(triangle, row + 1, col + 1, mem);    
30             mem[row][col] = triangle.get(row).get(col) + Math.min(left, right);
31         }
32         
33         return mem[row][col];
34     }
Solution - DFS, DP
Notice that in the above solution, we revisit each number multiple times which may not be necessary. For example, the sums in the small triangle
[
 [5]
[1,8]
]
has been recalculated along the path via number 3 and 4.

That hints us to use DP to optimize the algorithm.
Instead of recalculate all the time, we store the known minimun sum from the current node to bottom in a table. Then next time when we hit the same number, it only takes O(1) time to loop up the value.

 private int DFS(ArrayList<ArrayList<Integer>> triangle, int row, int column,  
     HashMap<Integer, Integer> rowMin) {  
   int min = triangle.get(row).get(column);  
   if (row == triangle.size() - 1) { // last row, return itself  
     return min;  
   }  
   
   if (!rowMin.containsKey(row+1)) { // calculate for first column  
     min += Math.min(DFS(triangle, row+1, column, rowMin),  
             DFS(triangle, row+1, column+1, rowMin));  
   } else {  
     min += Math.min(rowMin.get(row+1),  
             DFS(triangle, row+1, column+1, rowMin));  
   }  
   
   rowMin.put(row, min);  
   
   return min;  
 }  
   
 public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {  
   return DFS(triangle, 0, 0, new HashMap<Integer, Integer>());  
 }

Bottom-Up (Good Solution)
http://www.programcreek.com/2013/01/leetcode-triangle-java/
We can actually start from the bottom of the triangle.
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
 int[] total = new int[triangle.size()];
 int l = triangle.size() - 1;
 
 for (int i = 0; i < triangle.get(l).size(); i++) {
  total[i] = triangle.get(l).get(i);
 }
 
 // iterate from last second row
 for (int i = triangle.size() - 2; i >= 0; i--) {
  for (int j = 0; j < triangle.get(i + 1).size() - 1; j++) {
   total[j] = triangle.get(i).get(j) + Math.min(total[j], total[j + 1]);
  }
 }
 
 return total[0];
}

int minimumTotal(vector<vector<int> > &triangle) {
    int triangleSize = triangle.size();
    if(triangleSize == 0){
        return 0;
    }
    vector<int> saveMinDistance(triangle[triangleSize - 1].size() + 1, 0);
    int first,second,current;
    first = second = current = 0;
    for(int i = triangleSize - 1; i >=0; i--){
        for(int j = 0; j < i + 1; j++){
            current = triangle[i][j];
            first = current + saveMinDistance[j];
            second = current + saveMinDistance[j + 1];
            saveMinDistance[j] = first < second ? first : second;
        }
    }
    return saveMinDistance[0];
}

http://www.zrzahid.com/min-sum-path-in-triangle/
Notice that if we start from top and do a topdown dp then we might get wrong result as in example 2 it will return 15 = [2, 4, 5, 4]. But the actual minimum path is 13 = [2, 5, 5, 1]. That is we need to do a bottom-up computation for the dp. That is,
dp[level][i] = triangle[level][i] + min{dp[level+1][i], dp[level+1][i+1]}

//O(n^2) time and O(n^2) space for dp table
public static int triangleMinSumPath(List<int[]> triangle){
 int levels = triangle.size();
 int dp[][] = new int[levels][levels];
 
 dp[levels-1] = triangle.get(levels-1);
 
 //bottom up Dijkstra
 for(int l = levels-2; l>=0 ; l--){
  for(int i = 0; i<=l; i++){
   dp[l][i] = Math.min(dp[l+1][i], dp[l+1][i+1]) + triangle.get(l)[i];
  }
 }
 return dp[0][0];
}
O(n) space solution
If we print the dp table of the above code for example 2 then we will see the following –
Triangle - 

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


dp table  -

13,  0,  0, 0 
11, 13,  0, 0 
 6,  9, 10, 0 
 1,  4,  8, 3
If we look closely then we can see that the table has meaningful values in lower half only and at each level bottom up we have one of the column value getting fixed. So, we could have basically used the bottom level array as the dp table and at each level we update the columns bottom up. In this way we can decrease the space from O(n^2) to O(n). Below is the modified implementation of the above code by using O(n) space for dp table.
//O(n^2) time and O(n) space 
public static int triangleMinSumPath2(List<int[]> triangle){
 int levels = triangle.size();
 int dp[] = new int[levels];
 
 dp = triangle.get(levels-1);
 
 //bottom up Dijkstra
 for(int l = levels-2; l>=0 ; l--){
  for(int i = 0; i<=l; i++){
   dp[i] = Math.min(dp[i], dp[i+1]) + triangle.get(l)[i];
  }
 }
 return dp[0];
}
Read full article from Leetcode Triangle solution | easycpp
at
Labels: , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts