补一下
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];
}
