这个题目，我从前天晚上（8月6号晚上）调试到现在（8月8号16:21），太心酸了，不好好总结一下，就太对不起自己了！
这是题目：
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
动态规划，其实任何算法都是：核心思想+边界条件，其实不少的边界条件还是在调试过程中加上去的！！
该题，我参考了网上的不少博客，自己总结如下：
首先用一个二元数组来记录s和p的匹配情况（s代表源字符串，p代表目标字符串），比如res[i][j]为true表示 s[0... i-1]与p[0... j-1]已经匹配。
假设当前需要判定s[0 ...i]与p[0... j]是否匹配，也就是res[i+1][j+1]是否为true：
- 若p[j]=='*'
a. res[i+1][j]为true（此时*将其前面的那个字符只取1次）
| 0 | ..... | i-1 | i | ||
| 0 | ..... | j-1 | j * |
b. res[i+1][j-1]为true（此时*将其前面的那个字符一次也不取，即二者为空了）
c. res[i][j+1]为true且s[i]==s[i-1]且s[i-1]==p[j-1]。（此时'*'将其前面的一个字符取了2次）。而且c选项还可以继续递归下去。
（2）若p[j-1]=='.'
因为'.*'代表0个或多个'.'，这可以匹配任何字符，所以只要res[i+1][j-1]或者res[i+1][j]中任意一个为true，剩下的res[i+1][j+1],res[i+2][j+1]......res[s.length()][j+1]就都可置为true。
- 若p[j]!='*'
当（s[i]==p[j]或p[j]=='.'）且res[i][j]为true时，res[i+1][j+1]置为true。
最后return res[s.lenth()][p.length()]
下面这些是我主要的参考资料，先附上自己的代码：
1 class Solution { 2 public: 3 bool isMatch(string s, string p) { 4 //constexpr int len1 = static_cast<const int>(s.length()), len2 = p.length(); 5 //bool res[len1][len2] = { 0 }; 这儿自己原本是想直接用数组，但是数组下标是要求常量表达式的，着急啊，现在也没解决 6 int len1 = s.length() + 1, len2 = p.length() + 1; 7 vector<vector<bool>> res(len1, vector<bool>(len2, false)); 8 res[0][0] = true; 9 for (int i = 1; i < len2;i++)//没有这3句， "aab", "c*a*b" 会不通过 10 if (p[i - 1] == '*') 11 res[0][i] = res[0][i - 2]; 12 13 for (int j = 0; j < len2-1; j++) 14 { 15 16 if (p[j] == '*') 17 { 18 19 if (j>0&&p[j - 1] != '.') 20 { 21 for (int i = 0; i < len1-1; ++i) 22 if (res[i + 1][j - 1] || res[i + 1][j] ||i>0&& s[i - 1] == s[i] && s[i - 1] == p[j - 1]&& (res[i][j + 1]||res[i][j]))//这个地方一定要注意在具体的条件上加上限制就好了，千万别去将前面的for循环由i=0改为i=1 23 res[i + 1][j + 1] = true; 24 } 25 else 26 { 27 int i = 0; 28 // for (; i < len1;) 29 //if (!res[i+1][j - 1] && !res[i][j]) 30 // ++i; 这个地方竟然写了个死循环 31 while (j>0&&i < len1-1&&!res[i + 1][j - 1] && !res[i+1][j]) 32 ++i; 33 for (; i < len1-1; ++i) 34 res[i + 1][j + 1] = true; 35 36 } 37 } 38 else 39 { 40 41 for (int i = 0; i < len1-1;++i) 42 if ((s[i] == p[j] || p[j] == '.') && res[i][j]) 43 res[i + 1][j + 1] = true; 44 } 45 } 46 return res[len1 - 1][len2 - 1]; 47 } 48 };