[leetcode] #120 triangle

#120 Triangle

這題是給一個 triangle 結構的 list, 每個list長度對應他的depth, ex. list[i].size() = i-th depth+1, 求從root(1st list)走到 leaf (last list) 時的最小花費. 以下給兩種解法。值得注意的是用bottom-up 的解法很漂亮, 但是(1)邊界的node處理要小心；(2)作空間最佳化的思路也不是容易懂。

1:  public int minimumTotal(List<List<Integer>> a) {  
2:       if (a.size() == 0) {  
3:            return 0;  
4:       }  
5:       int c0 = 0, c1 = 0;  
6:       List<Integer> row = null;  
7:       for (int i=0; i<a.size(); i++) {  
8:            row = a.get(i);  
9:            for (int j=0; j< row.size(); j++) {  
10:                 if (j==0) {  
11:                      c0 = 0;  
12:                 } else {  
13:                      c0 = c1;  
14:                 }  
15:                 if (j<i) {  
16:                 }  
17:            }  
18:       }  
19:  }  
20:  public void traverse(List<List<Integer>> a, int depth, int i, int sum, Integer ret) {  
21:       List<Integer> row = a.get(depth);  
22:       sum += row.get(i).intValue();  
23:       if (a.size() == depth+1) {  
24:            if (ret == null)   
25:                 ret = new Integer(sum);  
26:            else if (sum < ret.intValue())  
27:                 ret = new Integer(sum);  
28:            return;  
29:       }  
30:       traverse(a, depth+1, i, sum, ret);  
31:       traverse(a, depth+1, i+1, sum, ret);  
32:  }  
33:  public int minimumTotalR(List<List<Integer>> a) {  
34:       Integer ret = null;  
35:       traverse(a, 0, 0, 0, ret);  
36:       return ret.intValue();       
37:  }