https://leetcode.cn/problems/wildcard-matching/description/
给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
示例 2：
输入：s = "aa", p = "*"
输出：true
解释：'*' 可以匹配任意字符串。
示例 3：
输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
提示：
0 <= s.length, p.length <= 2000
s 仅由小写英文字母组成
p 仅由小写英文字母、'?' 或 '*' 组成
解答
使用dp动态规划解决该题
dp[x][y] 表示 s[1~x] 与p[1~y] 是否匹配
那么有一下4种情况
1 p[y]是字母 且和s[x]相同 dp[x][y]=dp[x-1][y-1];
2 p[y]是字母但是和s[x]不相同
那么dp[x][y] =false(也就是0);
3 p[y]是?,那么无条件匹配 dp[x][y]=dp[x-1][y-1];
4 p[y]是，那么替代0个字符 dp[x][y]= dp[x][y-1]
替代多个字符 因为p[y]是， 任意dp[x-2][y]，dp[x-3][y],dp[x-4][y]...为真，均可以推导出dp[x-1][y]为真,
所以我们只有一个转移方程 dp[x][y] = dp[x-1][y]
class Solution {
public:
bool isMatch(string s, string p) {
vector<vector<int>> dp(s.size()+5, vector<int>(p.size()+5));
dp[0][0] = 1;
s.insert(s.begin(), '#');
p.insert(p.begin(), '#');
for (int i = 0; i < s.size(); i++) {
for (int j = 0; j < p.size(); j++) {
if (s[i] == p[j] || p[j] == '?') {
if (i >= 1 && j >= 1)
dp[i][j] |= dp[i - 1][j - 1];
}
else if (p[j] == '*') {
if (i >= 1)
dp[i][j] |= dp[i - 1][j];
if (j >= 1)
dp[i][j] |= dp[i][j - 1];
//if (i >= 1 && j >= 1)
//dp[i][j] |= dp[i - 1][j - 1];
}
}
}
//cout << dp[s.size() - 1][p.size() - 1] << endl;
return dp[s.size() - 1][p.size() - 1];
}
};