导读：算法哥最近几天非常忙，没来得及更新，很多粉丝私信催促算法哥，那今天就再来个有趣的动态规划吧！
题目描述
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。 '*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1:
输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入: s = "aa" p = "*" 输出: true 解释: '*' 可以匹配任意字符串。
示例 3:
输入: s = "adceb" p = "*a*b" 输出: true 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
题目分析
这个题目初步一看，很容易被吓到，因为这个题目有点正则表达式的意思在里面，大家知道正则表达式的语法可不简单，还好这个题目只是有一个简化版，问号匹配一个字符，星号匹配任意字符串！
遇到这种问题，不要畏惧，一定要抓住问题的本质，题目要求判断，给定的字符串s，是否可以被模式串p匹配。我们令字符串s的长度是s_len，模式串p的长度是p_len，题目的要求换句话说就是字符串s的前s_len个字符，要能被模式串p的前p_len个字符匹配！
为此，我们令dp[i][j]表示字符串s前i个字符，和模式串p前j个字符的匹配情况，匹配就等于1，否则等于0。我们所要求的就是dp[s_len][p_len]。既然是动态规划，我们就要有大问题转化成小问题，小问题推导大问题的思想！那dp[i][j]可以由哪些小问题推导过来呢？我们直接看状态转移方程式：
状态转移方程
显然，dp[i][j]可以由问题规模更小的dp[i-1][j-1]，dp[i][j-1]，dp[i-1][j]来推导！拿上面的状态转移方程来分析，当dp[i-1][j-1]等于1时，且p[j]等于问号或者星号或者p[j]等于s[i]时，dp[i][j]会等于1！类比我们可以分析其他两个状态的推导！
废话不多说，上源码：
源码
复杂度分析
根据给出的源码，两层for循环，负责度显然是O(mn)的，m表示字符串长度，n表示模式串长度！空间负责度也是O(mn)的，不过聪明的读者肯定发现这个也可以用算法哥在前面文章里经常说的滚动数组，把空间负责度降低成O(n)的，这个就留给读者自己思考吧！
题目总结
今天的这道题目，算法哥第一次看的时候差点被唬住了，其实leetcode hard模式的题目也不过如此嘛！哈哈！解决这个问题有以下几个难点：
1：抓住问题本质，化大问题变小问题，小问题推导大问题，这也是动态规划的核心；
2：结合问题的描述，顺理成章的找到那3个子状态，进行状态转移；
3：也是源码未给出的滚动数组的技巧就留给读者自己思考吧，如果有疑问，可以阅读算法哥前面提到过的文章；
题目分析完了，那就送算法哥上头条吧！您的关注，转发，点赞，评论都是对算法哥最大的鼓励！
,
