Triangle

。題目假設

在一組三角形數組裡找出一個最小路徑

。重要問題

。直覺

用動態規劃，最後一層是前一層的 cost 加上這層的最小值

。解決方法可行性

可行

。解決方案

從第一層開始，算出此層最小 cost，儲存在一個 list裡，

到第二層時，把上一層的 cost 加上這層的最小 cost，一路到最後一層

。資料結構

大小為三角形層數的一個數組

。複雜度

。遇到的困難點、想錯的地方

完全誤解題意....題目只能走「adjcent」位置，

所以想法要變成，對於從第二層開始，每一點要去計算自己和上一層相鄰最小cost，再記錄到一個 list 裡

重新寫的時後，「找上一層相鄰的元素」遇到了困難，我以為是 j-1, j+1，但其實是 j-1, j，

稍微想一下就知道為什麼了！

(另外如果用 List 版面會變得很複雜，最好用二維陣列)

public int minimumTotal(List<List<Integer>> triangle) {
    //find a min path => Cost(last row) = Cost(last row -1) + min(element of this row)
    if (triangle == null || triangle.size() == 0) {
        return -1;
    }

    List<List<Integer>> layerMin = new ArrayList<>();
    layerMin.add(new ArrayList<>(triangle.get(0)));
    for (int i=1; i<triangle.size(); i++) {
        List<Integer> lastLayerCost = layerMin.get(layerMin.size()-1);
        List<Integer> thisLayer = new ArrayList<>();
        //first
        thisLayer.add(triangle.get(i).get(0) + lastLayerCost.get(0));
        //last
        thisLayer.add(triangle.get(i).get(triangle.get(i).size()-1) + lastLayerCost.get(lastLayerCost.size()-1));
        for (int j=1; j<triangle.get(i).size()-1; j++) {
            thisLayer.add(j, triangle.get(i).get(j) + Math.min(lastLayerCost.get(j-1), lastLayerCost.get(j)));
        }
        layerMin.add(thisLayer);
    }

    int min = Integer.MAX_VALUE;
    for (int i=0; i<layerMin.get(layerMin.size()-1).size(); i++) {
        if (layerMin.get(layerMin.size()-1).get(i) < min) {
            min = layerMin.get(layerMin.size()-1).get(i);
        }
    }
    return min;
}