120. Triangle

1. 先写两个corner case压惊。
2. 思路，
   a. 因为找的是最小和的路径，所以路径中点上一层无非左上或者右上两点必须被选中。
   b. 类似贪婪的解法也不行，因为没法预测下面的数有多大。
   c. 只能稳扎稳打，比如第k行有k个数，用一个数组存储每一个位置“作为终点时，能够得到的最小和”，i.e. 也就是左上那个记录的数和右上选一个小的，再加上自己。
   d. 最后选出最后一行最小的。
3. 时间：第n行有n个数，都要扫过来，时间是 O(n2)。
4. 空间：按说是O(n2)，但是其实上面那排的结果扫完就不用了。可以被下一行覆盖。所以O(n)长度的数组就能解决问题。导致的问题就是：什么时候抹掉？ 第m行的第n个数，他是第m+1行的第n个数的右上角，第n+1个数的左上角，所以当第m+1行算到第n+2个数的时候，可以抹掉第m行的第n个数，当然是替换为第m+1行的第n个数。

public class Solution {
    public int MinimumTotal(IList<IList<int>> triangle) {
        //f(0) = 0
        if(triangle == null || triangle.Count <= 0){
            return 0;
        }
        //f(1) = 1
        if(triangle.Count == 1){
            return triangle[0][0];
        }
        
        int n = triangle.Count;
        int[] current_row_min = new int[n];
        int[] last_row_min = new int[n];
        last_row_min[0] = triangle[0][0];
        for(int level = 2; level <= n; level++){
            for(int col = 1; col <= level; col ++){
                if(col == 1){
                    current_row_min[col - 1] = last_row_min[col - 1] + triangle[level - 1][col - 1];
                }
                else if(col < level){
                    current_row_min[col - 1] = Math.Min(last_row_min[col - 2], last_row_min[col - 1]) + triangle[level - 1][col - 1];
                }
                else{
                    current_row_min[col - 1] = last_row_min[col - 2] + triangle[level - 1][col - 1];
                }
                if(col - 2 >= 0) {
                    last_row_min[col - 2] = current_row_min[col - 2]; //cache last row result
                }
                if(col == level){
                    last_row_min[col - 1] = current_row_min[col - 1];
                }

            }
        }
        int temp_min = current_row_min[0];
        for(int col = 1; col <= n; col++){
            temp_min = Math.Min(temp_min, current_row_min[col - 1]);
        }
        return temp_min;
    }
}