Problem description:
Level: easy
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
Example
For example, given the following triangle
|
1 2 3 4 5 6 7 8 |
[ [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).
Note
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
Solution:
Approach 1:
Dynamic programming: from bottom to top
Time: O(n^2)
add node value from the bottom to top level nodes
finally get a[0][0]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) { int n = triangle.size(); if(n == 0) return 0; for(int i = n-1; i > 0; i-- ) { for(int j = 0; j < i; j++) { int val = Math.min(triangle.get(i).get(j), triangle.get(i).get(j+1)) + triangle.get(i-1).get(j); triangle.get(i-1).set(j, val); } } return triangle.get(0).get(0); } |
Approach 2:
Dynamic programming: from top to bottom
Time: O(n^2)
hint: add from a[0][0] to bottom
in level n: return the minimum value
Approach 3:
Binary tree DFS traverse
Time: O(2^n), not efficient when n > 10
|
1 2 3 4 5 6 7 8 9 10 11 |
void dfs(int x, int y, int sum) { if(x ==n) {....} dfs(x+1, y, sum + a[x][y]); dfs(x+1, y+1, sum + a[x][y]); } int minpath() { return dfs(0,0,0); } |
Approach 4:
Binary tree DFS Divide & Conquer
Time: O(2^n), not efficient when n > 10
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
x, y is position n is total height int dfs (int x, int y) { if(x == n) return 0; return min(dfs(x+1, y), dfs(x+1, y+1)) + a(x,y) } int minpath() { return dfs(0,0); } |
