【题意】
给两个字符串s和p，判断s是否能用p进行匹配。
【题解】
dp[i][j]表示s的前i个是否能被p的前j个匹配。
首先可以分成3大类情况，我们先从简单的看起：
（1）s[i - 1] = p[j - 1]，易得dp[i][j] = dp[i-1][j-1]
（2）p[i - 1] = '.'，因为'.'可以匹配任何字符，所以dp[i][j] = dp[i-1][j-1]
（3）p[i - 1] = '*'，这种情况就比较复杂了。
当p[j - 2] != s[i - 1] && p[j - 2] != '.'时，即当s = aba，p = abb*这种情况，因为 * 可以代表0个或多个，所以当p[j -2] != s[i - 1]时，往回倒退2个即dp[i][j] = dp[i][j - 2]
然后除去这种情况还有3种匹配情况，只要满足以下任意一种情况也是成立的
当 * 匹配多个时：dp[i][j] = dp[i - 1][j]，即当s = abbb，p = ab*，因为b相等所以可以将s最后一个b删去，比较前面的abb与ab*从而实现 * 表示多个
当 * 匹配单个时：dp[i][j] = dp[i][j - 1]，即当s = aba，p = aba*
当 * 匹配0个时：dp[i][j] = dp[i][j - 2]，上面说过了
【代码】
1 class Solution { 2 public: 3 bool dp[35][35]; 4 bool isMatch(string s, string p) { 5 s = " " + s; 6 p = " " + p; 7 memset(dp , false, sizeof(dp)); 8 dp[0][0] = true; 9 int m = s.size(), n = p.size(); 10 for (int i = 1; i <= m; i++){ 11 for (int j = 1; j <= n; j++){ 12 if (s[i - 1] == p[j - 1])dp[i][j] = dp[i - 1][j - 1]; 13 else if (p[j - 1] == '.')dp[i][j] = dp[i - 1][j - 1]; 14 else if (p[j - 1] == '*'){ 15 if (s[i - 1] != p[j - 2] && p[j - 2] != '.') 16 dp[i][j] = dp[i][j - 2]; 17 else{ 18 dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j]; 19 } 20 } 21 } 22 } 23 return dp[m][n]; 24 } 25 };