[LeetCode] Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

思路1：DP

和Regular Expression Matching很像，这里的'?'相当于Regular Expression中的'.'，但'*'的用法不一样。这里'*'与前一个字符没有联系，并且无法消去前一个字符，但可以表示任意一串字符。递推公式的推导和Regular Expression Matching也基本类似。

p[j-1] == s[i-1] || p[j-1] == '?'：dp[i][j] = dp[i-1][j-1]

p[j-1] == '*'：

1. 匹配0个字符：dp[i][j] = dp[i][j-1]

2. 匹配1个字符：dp[i][j] = dp[i-1][j-1]

3. 匹配多个字符：dp[i][j] = dp[i-1][j]

先用二维数组写，发现会Memory Limit Exceeded

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: bool isMatch(const char *s, const char *p) { int m = strlen(s), n = strlen(p); vector<vector<bool>> dp(m+1, vector<bool>(n+1,false)); dp[0][0] = true; for(int i=0; i<m; i++) { for(int j=1; j<n; j++) { if(p[j-1]==s[i-1] || p[j-1]=='?') dp[i][j] = i>0 && dp[i-1][j-1]; else if(p[j-1]=='*') dp[i][j] = dp[i][j-1] || (i>0 && (dp[i-1][j-1] || dp[i-1][j])); } } return dp[m][n]; } };

然后用一维滚动数组改写，发现会Time Limit Exceeded

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: bool isMatch(const char *s, const char *p) { int m = strlen(s), n = strlen(p); vector<bool> dp(m+1, false); for(int i=0; i<m; i++) { bool diag = dp[0]; dp[0] = i==0 ? true : false; for(int j=1; j<n; j++) { int temp = dp[j]; if(p[j-1]==s[i-1] || p[j-1]=='?') dp[j] = i>0 && diag; else if(p[j-1]=='*') dp[j] = dp[j-1] || (i>0 && (diag || dp[j])); diag = temp; } } return dp[n]; } };

思路2：双指针扫描

用DP会TLE，那么一定有其他好的方法。

[LeetCode] Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

思路1: DP

关键在于如何处理这个'*'号。

状态：和Mininum Edit Distance这类题目一样。

dp[i][j]表示s[0:i-1]是否能和p[0:j-1]匹配。

递推公式：由于只有p中会含有regular expression，所以以p[j-1]来进行分类。

p[j-1] != '.' && p[j-1] != '*'：dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1])

p[j-1] == '.'：dp[i][j] = dp[i-1][j-1]

而关键的难点在于 p[j-1] = '*'。由于星号可以匹配0，1，乃至多个p[j-2]。

1. 匹配0个元素，即消去p[j-2]，此时p[0: j-1] = p[0: j-3]

dp[i][j] = dp[i][j-2]

2. 匹配1个元素，此时p[0: j-1] = p[0: j-2]

dp[i][j] = dp[i][j-1]

3. 匹配多个元素，此时p[0: j-1] = { p[0: j-2], p[j-2], ... , p[j-2] }

dp[i][j] = dp[i-1][j] && (p[j-2]=='.' || s[i-2]==p[j-2])

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { public: bool isMatch(const char *s, const char *p) { int m = strlen(s), n = strlen(p); vector<vector<bool>> dp(m+1, vector<bool>(n+1,false)); dp[0][0] = true; for(int i=0; i<=m; i++) { for(int j=1; j<=n; j++) { if(p[j-1]!='.' && p[j-1]!='*') { if(i>0 && s[i-1]==p[j-1] && dp[i-1][j-1]) dp[i][j] = true; } else if(p[j-1]=='.') { if(i>0 && dp[i-1][j-1]) dp[i][j] = true; } else if(j>1) { //'*' cannot be the 1st element if(dp[i][j-1] || dp[i][j-2]) // match 0 or 1 preceding element dp[i][j] = true; else if(i>0 && (p[j-2]==s[i-1] || p[j-2]=='.') && dp[i-1][j]) // match multiple preceding elements dp[i][j] = true; } } } return dp[m][n]; } };

思路2: 双指针扫描

LeetCode作者给的解法，非常巧妙：

http://leetcode.com/2011/09/regular-expression-matching.html

[LeetCode] Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

思路1：DP

求极值问题一般想到DP或Greedy，显然Greedy在这里不太适用，只有用DP了。

1. 状态：
DP[i]：以s[i-1]为结尾的longest valid parentheses substring的长度。

2. 通项公式：
s[i] = '('：
DP[i] = 0

s[i] = ')'：找i前一个字符的最长括号串DP[i]的前一个字符j = i-2-DP[i-1]
DP[i] = DP[i-1] + 2 + DP[j]，如果j >=0，且s[j] = '('
DP[i] = 0，如果j<0，或s[j] = ')'

......... (     x    x    x    x   )
          j                      i-2 i-1

证明：不存在j' < j，且s[j' : i]为valid parentheses substring。
假如存在这样的j'，则s[j'+1 : i-1]也valid。那么对于i-1来说：
(    x    x    x    x    x
j'  j'+1                  i-1
这种情况下，i-1是不可能有比S[j'+1 : i-1]更长的valid parentheses substring的。

3. 计算方向
显然自左向右，且DP[0] = 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: int longestValidParentheses(string s) { int n = s.size(), maxLen = 0; vector<int> dp(n+1,0); for(int i=1; i<=n; i++) { int j = i-2-dp[i-1]; if(s[i-1]=='(' || j<0 || s[j]==')') dp[i] = 0; else { dp[i] = dp[i-1]+2+dp[j]; maxLen = max(maxLen, dp[i]); } } return maxLen; } };

思路2：stack

括号题自然又想到了stack。仔细想下，这题目其实是Valid Parentheses的升级版。一个valid parentheses substring必然以'('开头以')'结尾，并且中间一定也是一个valid parentheses substring。这也意味着依照Valid Parentheses解法那样，用stack来存储没有配对的'('和')'，并用相应的')'来消去stack top的'('，最长substring的首尾必然会在这个过程中相消。

1. 由于我们需要知道它们之间的长度，所以stack里可以存储各个'('的坐标。
2. 为了能正确计算类似“ ) ( ) ( ) ”这种valid substring连接而组成的valid substring。我们必须也插入')'进stack，作为边界来计算长度。
3. 为了能在stack中区分左右括号，每个插入item定义为pair<int,int>。first为坐标，second表示左还是右括号。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: int longestValidParentheses(string s) { stack<pair<int,int>> stk; // first: index, second: 0:'(', 1:')' int maxLen = 0, curLen = 0; for(int i=0; i<s.size(); i++) { if(s[i]=='(') // left parenthesis stk.push(make_pair(i,0)); else { // right parenthesis if(stk.empty() || stk.top().second==1) stk.push(make_pair(i,1)); else { stk.pop(); if(stk.empty()) curLen = i+1; else curLen = i-stk.top().first; maxLen = max(maxLen, curLen); } } } return maxLen; } };

[LeetCode] Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

思路：

一看要求解的个数，然后又是string匹配，而且形式上和Minimum Edit Distance那题很像，基本就是DP题跑不了了。DP题惯例的三步走：定义状态，推导递推公式，确定状态计算方向和起始状态。

1. 状态：i, j分别表示T中长度为i的prefix：T[0:i-1]，和S中长度为j的prefix：S[0:j-1]。

DP[i][j]：S[0:j-1]中存在T[0:i-1]作为distinct subsequence的个数。显然如果j<i，DP[i][j] = 0。

2. 递推公式：

(a) T[i]!=s[j]:

T = r a b

S = r c a c b c

DP[i+1][j+1] = DP[i+1][j]

(b) T[i] = s[j]: 

T = r a b b

S = r a b b b  - DP[i+1][j] = 1

S = r a b b b  - DP[i][j] = 2

S = r a b b b  /

DP[i+1][j+1] = DP[i][j] + DP[i+1][j]

公式总结：
S[j-1]!= T[i-1]：DP[i][j] = DP[i][j-1]
S[j-1]==T[i-1]：DP[i][j] = DP[i-1][j-1] + DP[i][j-1]

3. 计算方向和起始状态：

DP[i][j]

DP[i+1][j]   DP[i+1][j+1]

所以从上向下，从左到右的顺序可以计算。

根据计算顺序，需要先设置第0行、0列的值。
第0列：DP[i][0] = 0，i>0。因为T的长度大于S的长度，不可能成为S的subsequence。
第0行：DP[0][j] = 1，j>=0。这是为了保证第1行的计算正确：

T = r
S = r a r b r c

      r a  r b r  c  
  1 1 1 1 1 1 1
r 0 1 1 2 2 3 3

4. 计算优化：用滚动数组减少内存消耗。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: int numDistinct(string S, string T) { int n = S.size(), m = T.size(); vector<int> dp(n+1, 1); for(int i=1; i<=m; i++) { int upLeft = dp[0]; dp[0] = 0; for(int j=1; j<=n; j++) { int temp = dp[j]; dp[j] = dp[j-1]; if(S[j-1]==T[i-1]) dp[j] += upLeft; upLeft = temp; } } return dp[n]; } };

[LeetCode] Palindrome Partitioning I, II

Palindrome Partitioning I

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

思路：Palindrome Partitioning I

遇到要求所有组合、可能、排列等解集的题目，一般都是用DFS + backtracking来做。要分割回文的前提是能够判断回文。在做DFS的时候，如果每次从start出发查找s[start:end]是否是回文，会使算法复杂度大大增加。而在Longest Palindromic Substring这题中已经知道如何用DP来计算任意s[i:j]是否是回文。因此可以先计算该判断矩阵，在DFS的时候用来剪枝，大大提高效率。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution { public: vector<vector<string>> partition(string s) { int n = s.size(); vector<vector<string>> ret; vector<string> sol; vector<vector<bool>> isPal(n, vector<bool>(n,false)); for(int i=n-1; i>=0; i--) { for(int j=i; j<n; j++) { if((i+1>=j-1 || isPal[i+1][j-1]) && s[i]==s[j]) isPal[i][j] = true; } } findPartitions(s, 0, isPal, sol, ret); return ret; } void findPartitions(string &s, int start, vector<vector<bool>> &isPal, vector<string> &sol, vector<vector<string>> &ret) { if(start==s.size()) { ret.push_back(sol); return; } for(int i=start; i<s.size(); i++) { if(isPal[start][i]) { int len = i-start+1; sol.push_back(s.substr(start, len)); findPartitions(s, i+1, isPal, sol, ret); sol.pop_back(); } } } };

思路：Palindrome Partitioning II

整体的思路是一维DP。DP[i]表示长度为i的prefix：s[0: i-1]的min cut数量。
DP[i] = min (DP[j] + 1) ，对所有 0<=j<i，且s[j: i-1]为palindrome。
和I同样的技巧，用DP先计算存储一个palindrome判断矩阵isPal[i][j]，便于后面一维DP计算中能迅速判断s[j: i-1]是否为palindrome。

有一个更优的解法参考：
https://oj.leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public: int minCut(string s) { int n = s.size(); if(n<=1) return 0; vector<vector<bool>> isPal(n, vector<bool>(n, false)); for(int i=n-1; i>=0; i--) { for(int j=i; j<n; j++) { if((i+1>j-1 || isPal[i+1][j-1]) && s[i]==s[j]) isPal[i][j] = true; } } vector<int> dp(n+1,INT_MAX); dp[0] = -1; for(int i=1; i<=n; i++) { for(int j=i-1; j>=0; j--) { if(isPal[j][i-1]) { dp[i] = min(dp[i], dp[j]+1); } } } return dp[n]; } };

[LeetCode] Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

思路：

很多算法教科书上都有的经典二维DP问题。

1. 状态：

DP[i+1][j+1]：word1[0:i] -> word2[0:j]的edit distance。

2. 通项公式：

考虑word1[0:i] -> word2[0:j]的最后一次edit。无非题目中给出的三种方式：

a) 插入一个字符：word1[0:i] -> word2[0:j-1]，然后在word1[0:i]后插入word2[j]

DP[i+1][j+1] = DP[i+1][j]+1

b) 删除一个字符：word1[0:i-1] -> word2[0:j]，然后删除word1[i]

DP[i+1][j+1] = DP[i][j+1]+1

c) 替换一个字符：word1[0:i-1] -> word2[0:j-1]

word1[i] != word2[j]时，word1[i] -> word2[j]：DP[i+1][j+1] = DP[i][j] + 1

word1[i] == word2[j]时：DP[i+1][j+1] = DP[i][j] 

所以min editor distance应该为：

DP[i+1][j+1] = min(DP[i][j] + k, DP[i+1][j]+1, DP[i][j+1]+1) 

word1[i]==word2[j] -> k = 0, 否则k = 1

3. 计算方向：

replace (i, j)      delete (i, j+1)

insert (i+1, j)    (i+1, j+1)

可见要求DP[i+1][j+1]，必须要知道二维矩阵中左上，上方和下方的3个值。所以当我们确定第0行和第0列的值后，就可以从上到下、从左到右的计算了。

4. 起始、边界值

DP[0][i] = i： word1为空，要转化到word2[0:i-1]，需要添加i个字符。

DP[i][0] = i： word2为空，要从word1转化到空字符串，需要删除i个字符。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); for(int j=1; j<=n; j++) dp[0][j] = j; for(int i=1; i<=m; i++) { dp[i][0] = i; for(int j=1; j<=n; j++) { dp[i][j] = dp[i-1][j-1]; if(word1[i-1]!=word2[j-1]) dp[i][j]++; dp[i][j] = min(min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i][j]); } } return dp[m][n]; } };

[LeetCode] Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

思路：

假设解码函数为h。对于一位数X，只能解码成h[X]。而对于一个两位数XY：

1. 如果XY<=26，那么能解码成h[X], h[Y], h[XY]

2. 否则，只能解码成h[X], h[Y]

由于只要求计算最多的解码方法而并不要求每种解码的结果，所以用DP做更为合适高效。

定义dp[i+1]为能解码长度为i+1的string s[0:i]的方法数：

1. dp[0] = 1，dp[1] = 0

2. v = s[i-1]*10+s[i]：

v<=26： dp[i+1] = dp[i] + dp[i-1]

v>26：dp[i+1] = dp[i]

corner case：有0的情况

Y = 0：显然无法解码成h[Y]，此时只能看h[XY]是否valid：dp[i+1] = dp[i-1]

X = 0：显然无法解码成h[XY]，此时dp[i+1] = dp[i]

整理总结corner case：

XY可以解码的条件是：9<XY<=26

Y可以单独解码的条件是：Y != '0'

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: int numDecodings(string s) { if(s.empty() || s[0]<'1' || s[0]>'9') return 0; vector<int> dp(s.size()+1,0); dp[0] = dp[1] = 1; for(int i=1; i<s.size(); i++) { if(!isdigit(s[i])) return 0; int v = (s[i-1]-'0')*10 + (s[i]-'0'); if(v<=26 && v>9) dp[i+1] += dp[i-1]; if(s[i]!='0') dp[i+1] += dp[i]; if(dp[i+1]==0) return 0; } return dp[s.size()]; } };

[LeetCode] Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

思路：

一开始觉得是一维DP。dp[i]记录以i为结尾的最长回文的长度，然后有通项公式：

dp[i] = dp[i-1] + 2，如果s[i] = s[j]，j = i - dp[i-1] - 1。否则为dp[i] = 1

例如：a b c b a d
p[3] = 3 && s[4] = s[0] => dp[4] = 5

但是仔细一想，当s[i] != s[j]时，dp[i]实际是无法确定的。

例如：b a c c a c
dp[4] = 4 (a c c a)，但s[5] != s[0]，而实际dp[5] = 3因为s[5] = s[3]，且s[4:4]是回文。

因此这题不是简单的一维DP，而是二维DP，需要计算并记录任意s[i:j]是否是回文：

定义bool isPal[i][j]表示s[i:j]是否为回文，isPal[i][j] = true需要满足两个条件: 
1. s[i] ==s[j]
2. i+1>j-1或 isPal[i+1][j-1] == true (即s[i+1 : j-1]是回文)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: string longestPalindrome(string s) { if(s.size()<=1) return s; int start = 0, maxLen = 1, n = s.size(); bool isPal[1000][1000] = {false}; for(int i=n-1; i>=0; i--) { for(int j=i; j<n; j++) { if((i+1>j-1 || isPal[i+1][j-1]) && s[i]==s[j]) { isPal[i][j] = true; if(j-i+1>maxLen) { maxLen = j-i+1; start = i; } } } } return s.substr(start,maxLen); } };

[LeetCode] Unique Paths I, II

Unique Paths I

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

思路：Unique Paths I

Climbing Stairs二维版。计算解个数的题多半是用DP。而这两题状态也非常显然，dp[i][j]表示从起点到位置(i, j)的路径总数。DP题目定义好状态后，接下去有两个任务：找通项公式，以及确定计算的方向。

1. 由于只能向右和左走，所以对于(i, j)来说，只能从左边或上边的格子走下来：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

2. 对于网格最上边和最左边，则只能从起点出发直线走到，dp[0][j] = dp[i][0] = 1

3. 计算方向从上到下，从左到右即可。可以用滚动数组实现。

1 2 3 4 5 6 7 8 9 10 11 12 13

class Solution { public: int uniquePaths(int m, int n) { if(m<1 || n<1) return 0; vector<int> dp(n, 1); for(int i=1; i<m; i++) { for(int j=1; j<n; j++) { dp[j] += dp[j-1]; } } return dp[n-1]; } };

思路：Unique Paths II

与I有两点不同：

1. 当(i, j)有障碍时dp[i][j] = 0

2. dp[0][j]和dp[i][0]未必为1.

dp[0][j] = obstacleGrid[0][j] ? 0 : dp[0][j-1]

dp[i][0] = obstacleGrid[i][0] ? 0 : dp[i-1][0]

3. 当obstacleGrid [0][0] = 1时，return 0

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { if(obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0]==1) return 0; int m = obstacleGrid.size(), n = obstacleGrid[0].size(); vector<int> dp(n,1); for(int j=1; j<n; j++) { if(obstacleGrid[0][j]==1) dp[j] = 0; else dp[j] = dp[j-1]; } for(int i=1; i<m; i++) { dp[0] = obstacleGrid[i][0]==1 ? 0 : dp[0]; for(int j=1; j<n; j++) { dp[j] = obstacleGrid[i][j]==1 ? 0 : dp[j-1] + dp[j]; } } return dp[n-1]; } };

[LeetCode] Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

思路：

这题用到了一点DP的思路，即存储每一层的结果，来计算下一层。关键点在于要用O(n) space。用两个数组prePath和curPath分别存储上一层和本层的每个坐标的min path sum。如果已知prePath，则可以计算curPath：

1. 对第j层 (j = 0 ~ n-1)，一共有j+1个数：0:j。而上一层有j个数：0:j-1

2. 除去头尾两个数外，curPath[i] = min(prePath[i-1], prePath[i]) + triangle[j][i]

3. 头尾的特殊情况：curPath[0] = prePath[0] + triangle[j][0]；curPath[j] = prePath[j-1] + triangle[j][j]

4. 在计算下一层前，需要交换curPath和prePath。

5. 在最后一层curPath计算结束后，在其中找一个最小值即为整个树的min path sum。

额外存储空间是2n。尽管通过滚动数组也可以事先n，但代码要复杂很多，面试短时间内容易出错。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { if(triangle.empty()) return 0; int n = triangle.size(); vector<int> curPath(n,INT_MAX); vector<int> prePath(n,INT_MAX); curPath[0] = triangle[0][0]; for(int lvl=1; lvl<n; lvl++) { prePath = curPath; curPath[0] = prePath[0] + triangle[lvl][0]; curPath[lvl] = prePath[lvl-1] + triangle[lvl][lvl]; for(int i=1; i<lvl; i++) curPath[i] = min(prePath[i-1], prePath[i]) + triangle[lvl][i]; } int minPath = INT_MAX; for(int i=0; i<n; i++) minPath = min(minPath, curPath[i]); return minPath; } };