**reference: **https://leetcode.com/problems/wildcard-matching/
dynamic programming 解法：https://www.youtube.com/watch?v=3ZDZ-N0EPV0
注：此解的空间复杂度仍不符合要求，进一步优化空间复杂度可以复用dp数组，可以降空间复杂度从O(MN)降为O(2N)
class Solution
{
public:
bool isMatch(string s, string p)
{
if (s.empty() && p.empty())
return true;
int idx = 1;
for (int i = 1; i < (int)p.length(); ++i)
{
if (!(p[i] == '*' && p[i] == p[idx - 1]))
p[idx++] = p[i];
}
p.erase(p.begin() + idx, p.end());
int m = s.length() + 1;
int n = p.length() + 1;
vector<vector<int>> dp;
dp.resize(m);
for (int i = 0; i < m; ++i)
dp[i].resize(n);
dp[0][0] = 1;
if (p[0] == '*')
dp[0][1] = 1;
for (int i = 1; i < m; ++i)
{
for (int j = 1; j < n; ++j)
{
char chs = s[i - 1];
char chp = p[j - 1];
if (chp == '?' || chp == chs)
{
dp[i][j] = dp[i - 1][j - 1];
}
else if (chp == '*')
{
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
};
此处当p[j]为 * 时，动态规划的状态方程是 dp[i][j] = dp[i - 1][j] || dp[i][j - 1];之前好奇为什么不是dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1];，其实前者已经包括了后面的方程，在求值dp[i - 1][j]时，dp[i - 1][j] = dp[i - 2][j] || dp[i - 1][j - 1]
