8.4 extra added later

补一下

1] Min Stack

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;
    stack<int> mins;
    MinStack() {
    }
    
    void push(int x) {
        s.push(x);
        if (mins.empty() || mins.top()>=x) mins.push(x);
    }
    
    void pop() {
        if (!s.empty()) {
            if (mins.top()==s.top()) mins.pop();
            s.pop();
        }
    }
    
    int top() {
        if (!s.empty()) return s.top();
        return -1;
    }
    
    int getMin() {
        if (!mins.empty()) return mins.top();
        return -1;
    }
};

2] Minimum Path Sum

这么简单的dp做这么久不开森，，练练练
。。。minpath递增着index不是一样的吗orz

optimize: see hint at the end https://discuss.leetcode.com/topic/15269/10-lines-28ms-o-n-space-dp-solution-in-c-with-explanations/2
(keep only two arrays)

    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int dp[m+1][n+1];
        dp[m-1][n-1] = grid[m-1][n-1];
        for (int i=n-2; i>=0; --i) {
            dp[m-1][i] = grid[m-1][i] + dp[m-1][i+1]; 
        }
        for (int j=m-2;j>=0; --j) {
            dp[j][n-1] = grid[j][n-1] + dp[j+1][n-1];
        }
        
        for (int i=n-2; i>=0; --i) {
            for (int j=m-2; j>=0; --j) {
                dp[j][i] = grid[j][i] + min(dp[j+1][i], dp[j][i+1]);
            }
        }
        return dp[0][0];
    }