这道题的入手点是当做双序列的DP问题来做。设计dp[i][j]表示s的前i个元素、p的前j个元素能否匹配。（注意，预先调整成为1-index）
分析转移方程的时候，依然是关注s的第i个元素，p的第j个元素。其中p[j]是关键，因为它可能是通配符。所以常规的思路是：
- 如果p[j]='?'，它必须匹配s的第i个元素，显然dp[i][j]=dp[i-1][j-1].
- 如果p[j]='*'，它可以匹配s结尾的任意多个元素，所以有：
for (int k=0; k<=i; k++)
if (dp[k][j-1]==1) dp[i][j]=1;- 如果p[j]是普通字符，则必须与s的第i各元素完全一致。所以
if (s[i]==p[j])
dp[i][j]=dp[i-1][j-1]接下来考虑两个问题。首先是边界条件。最常见的dp[0][0]=1是必然的。但同时要注意到第二种情况时，我们会查看dp[0][j-1]，而这个是未定义的。事实上dp[0][x]对任何的j而言不一定是0，比如当
s = ""
p = ****
所以我们需要对所有的dp[0][x]设计初始值。只有当p的前若干个都是星号时，才有dp[0][x]=1.
另外一个问题，就是如何改进第二种情况。用一个for循环是比较低效的，其实有一个更优秀的判定手段。
我们知道，当p[j]=='*'的前提下，我们有dp[i][j] = dp[0][j-1] || dp[1][j-1] || dp[2][j-1] || ... || dp[i-1][j-1] || dp[i][j-1]。
我们将i用i-1替换，就同理可以写出dp[i-1][j] = dp[0][j-1] || dp[1][j-1] || dp[2][j-1] || ... || dp[i-1][j-1]。
用第二式替换第一式右边的大部分项，就有dp[i][j] = dp[i-1][j] || dp[i][j-1].惊喜不惊喜？