打算背诵wildcard matching和regular expression matching

如题，做了一天要挂掉的感觉，看答案的code就觉得确实是这么回事，自己就是想不出来，第二次做背下来了。。。反正code不长，打算像背陋室铭一样背诵下来，刻骨铭心，以前上学那么多课文都通篇背下来了，还差这一两道题吗。。。

这两个题真的第一次做完全懵逼，后面几次做也很难一下子想出来。
但是反正就记住是从后往前去做dp，然后dp的条件很巧妙比较难想，多练几次感觉对提升dp的能力很有帮助

想算法是聪明人的事，我们需要做的就是 背诵 + 肌肉记忆

确实很不直观。
我尝试用数学推导来讲一遍wildcard matching。
首先，dp[j]的意义是对于s[0, i) 和 p[0, j)是否匹配。
然后就可以分情况讨论了。
如果s == p[j] 或者  p[j] == '?'的时候，就只需要看前面是否匹配，即dp[i + 1][j + 1] = dp【i】[j];
最tricky的一种情况是p[j] == '*'的时候，根据题意，这个可以match任意长度的字符串。
所以，

1. dp[i + 1][j + 1] = dp[i + 1][j] OR （dp[i][j] OR dp[i - 1][j] OR ... OR dp[0][j]）
   

复制代码

也就是这么多情况只要有一种是true就可以。我们看一下，dp[j + 1]是什么呢，只需要把上面那个式子中i代换成i - 1即可
[i]

1. dp[i][j + 1] = dp[i][j] OR dp[i - 1][j] OR ... OR dp[0][j]
   

复制代码

所以，

1. dp[i + 1][j + 1] = dp[i + 1][j] OR dp[i][j + 1]
   

复制代码

就是把第一个式子的后面括号里面那么多项等价代换一下。
不知道这样会不会更清楚一些。

楼主可以看看这个视频，https://www.youtube.com/watch?v= ... oy-CodingMadeSimple