leetcode 10.正则表达式匹配

思路：
动态规划 --- 自底向上（具体到抽象）
状态表示：dp[i][j]表示s的前i个能否被p的前j个匹配
状态转移：
已知：dp[i-1][j-1] -> dp[i][j]

1. p[j] == s[i] or p[j] == '.':dp[i][j] = dp[i-1][j-1]
2. p[j] == '':
   2.1 p[j-1] != s[i]:dp[i][j] = dp[i][j-2]
   //号前一个字符匹配不上，号匹配了0次，应该忽略这两个字符
   2.2 p[j-1] == s[i] or p[j-1] == '.':
   //号前面的字符可以与s[i]匹配，这种情况下，号可能匹配了前面的字符0个，也可能匹配前面的字符多个。
   //当匹配0个时，如ab -> abb 或者ab -> ab.，这时需要去掉p中的b或者.后进行比较，即dp[i][j] = dp[i][j-2]
   //当匹配多个时，如abbb -> ab，需要将s[i]前面的与p重新比较。即dp[i][j] = dp[i-1][j]

动态规划 --- 自顶向下（抽象到具体）
状态表示：dp[i][j]表示p从j开始到结尾，是否能够匹配s从i开始到结尾
状态转移：
已知：dp[i+1][j+1] -> dp[i][j]

1. p[j+1] != '*' :
   1.1 s[i] == p[j]:dp[i][j] = dp[i+1][j+1]
2. p[j+1] == '*':
   2.1 s[i] == p[j]:dp[i][j] = dp[i+1][j]
   2.2 s[i] != p[j]:dp[i][j] = dp[i][j+2]