leetcode10正则表达式匹配dp[i[门都示在S[阿时)。
大家好，我是leet。今天给大家带来一个第十题，流号正则表达式匹配了一道题，这题是一个困难题，我觉得是流号里面。我做到目前为止最难的一道题，因为他要考虑的。如果你按普通思路来看，他要考虑的情况太多了，在星号这一个步骤的时候，他考虑的情况特别多。
所以现在网上看了一下，普遍都是用动态规划来解这道题。我就说一下我的理解。首先，动态规划就是要满足最优子结构嘛。最优子结构的意思就是，当p对s识别的过程中，比如说p识别了p，e识别了s，然后到p2的时候，如果p.p上减二识别成功了，i减二的时候，就说明他的那些子集也是识别成功的，就是这样的意思。所以这题可以满足用动态规划的一种方式。
第二，什么时候用动态规划？就是它可能对应着很多种情况，当前就是用两个，用两个数指针就很难辨认出来他所有的情况的时候，可能用动态规划，然后利用他的最优子结构，可能会更好解一点。
为什么呢？因为动态规划是用了二维的数组，解了一维的问题，二维速度解一维问题，就可以在一个比较大的空间，就把这些所有的情况罗列出来了，我感觉是一个空间换时间的一种方式。
然后我们来讲一下，怎么用动态规划来解这道题？首先，要把所有情况都列出，然后这道题用动态规划，有一个很巧妙的方递推式，待会也会就是退一下。
·第一点就是现在明确dp数组就是动态规划，主要的一个数组，他ij就表示在当前的情况。pj已经匹配到si了，就是dpij，然后它是一个布尔型的，布尔型的一个数组，当他的比如说这个零的时候等于一，就说明它是零零的时候，这个就是匹配成功的。
然后我们接下继续看举例子。
·第一点就是他给这些要根据这里来举出那种分类。
→第一点就是当pj为普通字符的时候，这个时候假设对应的si，假设对应的si，假设一个动态规划，这个时候首先要保证的就是dp，a减1-1要满足对吧？并且怎么写？假设是 and 吧，并且就是pj等于si，或者pj等于点。
假设这种情况就是i j，就是pj跟si匹配的情况就把它缩写成这样，后面好写一点。
→第二个情况就是pj为点字符的时候，这个情况就是他已经满足了一个，因为它是点，就代表他匹配任意单个字符，所以他已经满足了一个这个条件，只用i减一和z减一成立就行了。这个时候dp，z就等于这个。上面就是就这种情况下dpij就等于这种。
→第三种情况就是当pj为新号字符的时候，就有很多种情况了。
→第一种就是pj跟pj减一，这个是p是新，dP然居他这里这个是一个字母假设是一个a，它不匹配。是什么意思？就是经过一定的判断，把这一个星代表零个a抛弃掉了，所以这个时候只用看dpi和z减二的值。
·这种情况下，当 p j 和 p j 减一匹配 s里面的一个字母的时候，首先要判断这两个是不是符合最优子结构的情况下，dp i 减一和z 减二，并且i z 减一跟东西是不是相等，如果相等就是第二种情况，剩下这个新号就可以去掉了，这是考虑第二种情况了。
·第三种情况就是p j 减一匹配s里面多个字母，这个时候涉及到比较复杂的情况，怎么样复杂法？首先来讲是不是等于把前面两个情况汇合起来。第一个情况就是dpi减二，不匹配s4的时候，然后或者d p i 减一，这一减二，i 这一减一对不对。
·第二种情况，匹配s里面一个字母的时候或者匹配s里面的两个字母，d p匹配两个字母的情况是用a行匹配两个字母，a对，只用看a减二跟z减二，这个时候就是dpi减二，并且i减一跟j减一，并且i和j减一是不是相等？然后就是三个或者d p等等，这就是多个的情况。
这就是普遍的解，为什么要写这个普遍解？到时候要推导出来，要推导出来当它是一个把这个删掉麻烦。因为正常来讲要每举出匹配s里面多个字母的情况的时候，可能会要每举出无限个，比如说匹配两个、三个、四个、五个，你想这是两个、还有三个、四个、五个、六个，那我要这样枚举。不说机器跑不跑得出来，人人肯定会累死。
所以为什么一开始看到这题，不会用这个动态规划去做这道题，因为就是可能情况实在太多了，我觉得可能二维都解不出，但是它这边有个非常巧妙的一点，这也是这道题里面最难最难的地方，就是把它这个地推式化解了。就是想过这是列出来的一个，上面这个是列出来的，一般是知道后面还有一堆。如果再列一个dpi减一，这种情况是什么？就是把i变成i减ej不变，就是第一批就照抄i减一，j减二或者第一批a减二，j减二，并且a减一再减一。
可以看到列举出dpi减一，这一之后就会发现这一部分跟这一部分是一样的，这一部分跟这一部分是一样的。唯一不同的就是多了一个i和j减一对，这个时候就可以通过这两个式子，用数学归纳法算出来dpi，d等于，d-i-i减e或者d-i-i-减e，并且这一件e就完了。d-i-i-d-i-s就是d-t之后的一个式子，就说匹配多个字母的一种情况，已经被数学归纳法简化成了两个条件语句。
所以说这就是这题的一个巧妙之处。然后这就是所有的一种情况，然后我们再进行代码的一个讲解。