困难 警告！

想都不要想，直接看答案

本文答案参考自leetcode官方

【方法一】动态规划（DP）

动态规划的一般解法：

1. 创建二维数组存放某些东西
2. 确定状态转移方程
3. 确定边界条件
4. 开始

对这道题，这个二维数组 f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配

1. 如果 s 的第 i 个字符与 p 的第 j 个字符相同，则 f[i][j] = f[i - 1][j - 1] ，因为你后面匹配了那前面也肯定匹配
2. 如果 s 的第 i 个字符与 p 的第 j 个字符不相同，则 f[i][j] = false
3. 如果 p 的第 j 个字符是 *，在匹配不到（0次）的情况下， f[i][j] = f[i][j - 2]，即星号和前面的字符相当于不存在（不影响结果）
4. 如果 p 的第 j 个字符是 *，在匹配到 1次 的情况下 ，f[i][j] = f[i][j - 2]
5. 如果 p 的第 j 个字符是 *，在匹配到（多于1次，设为n）的情况下 f[i][j] = f[i - n][j - 2]，同样是因为后面匹配了那前面也肯定匹配，这里具体操作是循环执行 f[i][j] = f[i - 1][j] n - 1次，然后执行 f[i][j] = f[i][j - 2]，官方给出了精巧的状态转移方程：（我难以表达出其精巧之处，反正就是精巧）

6. 如果 p 的第 j 个字符是 . ，则必定匹配

最终状态转移方程为：

这里最好结合画图来理解（但是我懒~）

边界条件为：f[0][0] = true

答案为 f[m][n] ，其中 m 和 n 分别是字符串 s 和 p 的长度

因为本人水平有限，如果以上内容有误，不用走程序，直接骂吧~[捂脸]