这道题一般有两种解法，一种是递归，比较好理解，另一种是动态规划。这里主要帮助自己顺了一下动态规划的逻辑。理解动态规划的时候，反复看了很多解释，才能彻底理清思路。
首先，我们定义dp[i][j]，用来表示p的前j个字符串与s的前i个字符串的匹配程度。字符串中有三种字符类型，自然就先分为三种情况讨论。
1. 当p[j]和s[i]的字符都为字母时，只需要判定p[j]是否等于s[i]。如果相等，则dp[i][j] = dp[i-1][j-1]。比如s='aebc'，p='adbc'，当p[2]和s[2]相等时，那么我们只需要看p[:2]与s[:2]是否相等就行。
2.当p[j]等于'.'时，那么它可以匹配任意字符，因此也就代表此时的p[j]一定等于s[i]，那这其实可以和第一种类型合并。
3. 当p[j]等于'*'时，由于*匹配的是前一个字符，于是需要分析p[j-1]与s[i]是否相等，因此需要分两种情况来讨论。
3.1. 当p[j-1]等于s[i]时，那么*有能力去匹配字符，并有三种匹配方式。第一种是不匹配，也就是让前一个字符也消失。比如s='...ba'，b='...ba*'，此时，如果我选择不匹配，那么我只需要看'...ba'与'...b'是否匹配，于是dp[i][j] = dp[i][j-2]。第二种是我只匹配一个字符，也就是此时，我只需要看'...ba'与'...ba'是否匹配，于是dp[i][j] = dp[i][j-1]。第三种，我想要用*匹配多次前一个字符，也就是说，我现在用当下的a*匹配完s[i]也就是字符a以后，我再用a*去匹配s[i-1]，也就是字符'b'。于是转移方程就变成了dp[i][j] = d[i-1][j]。
3.2. 当p[j-1]不等于s[i]时，此时 *不能去匹配字符，也就是说，我希望它匹配0次字符。因此由3.1的分析可以得到dp[i][j] = dp[i][j-2]。
这就是方程的主体了，那在写代码的时候需要考虑一些边界条件。为了让代码看起来更工整，我在p和s的开头都加上一个空字符。于是dp[0][0]一定等于True。然后初始化dp，所有的值为False。
在主体当中，为了避免讨论边界条件，将i和j都从1开始讨论。
此时考虑一种边界情况，也就是当s只剩下一个空字符时：s=' '，p=' a*'。此时dp[0][2]应该等于dp[0][0]，也就是让两个空字符去匹配。
结合一下所有情况，完整的代码如下：
下面举个例子，画一下dp的图，来更直观解释一下代码：
