LeetCode-10. 正则表达式匹配匹配，题目内容如下：
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '' 的正则表达式匹配。
'.' 匹配任意单个字符
'' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
由于题目是要求以正则串来匹配，那么我们以正则串为主，根据正则串的每个字符选择相应的策略来匹配需要匹配的字符串。题解中给出的是正则表达式匹配题解。关于动态规划算法，是一个比较难以理解的算法，通过查阅资料和习题练习，有助于掌握动态规划算法的思想。学习动态规划之前不能一蹴而就，直接上手动态规划，应该从简单的开始，斐波那契数列就是一个很好的例子，最开始使用递归，然后分析递归中的每一个步骤，可以发现很多步骤都是重复计算的过程，因此进行优化，变成记忆化+递归，然后再尝试去转换成动态规划。
回到这道题本身，我们在匹配的时候，先以最简单的问题开始，不考虑特殊规则时，是逐字匹配。以匹配串和正则串为x轴和y轴，建立一个二维数组，每一个字符互相对应一个格子，如果某个字母与上面的能够匹配上，并且前面的串已经匹配成功，因此前面的串加上这个字符仍然能够完全匹配。以最简单的两个单字符匹配为例，如图：
起始状态设置为空串，两个空串是能够匹配的，因此第一个位置是true，而空串不能够与任意字符匹配，因此第一行与第一列的其他均为false。那么在匹配当前字符时，发现这两个字符相同，并且这两个字符之前的串是完全匹配的，即dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)，因此在上图留空的位置应该为true，所以a == a，答案显而易见，但是我们可以通过这样的思路来解决正则表达式匹配的问题。
不难发现，这个动态规划的二维数组里面存储的是s串中前i项与p串中前j项是否可以匹配，这就是动态规划中的状态。接下来我们需要通过题设的条件，找出根据前面状态计算后面状态的方法，这种方法即是状态转移方程。剩下的就是处理动态规划的边界值问题了。
在这道题中通过前面的分析，再对题设条件找出对应的几种情况的状态转移方程。
.能够匹配任意单个字符，那么遇到这个符号，都属于可以匹配，因此这个符号为必定匹配，将其归至其他匹配的判断中。*的情况需要考虑两个因素，前一个字符不匹配的情况和多个字符匹配的情况。首先考虑前一个字符不匹配，那么有了这个星号，只要前面的是匹配的，则这个不匹配字符可以忽略，即dp[i][j - 2]。考虑多个字符匹配的情况，s串中的当前字符与p串星号前一个字符匹配，并且s串中前面的串或者前一个字符能够匹配上，则这个字符也能匹配，即dp[i - 1][j] || dp[i][j - 2]。
看到这里，不了解动态规划的人可能已经懵逼了，因为动态规划常常需要一些经验才能很好的运用，具体实现代码如下：
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for(int i = 0; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2];
if(match(s, p, i, j - 1)) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else {
if(match(s, p, i, j)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
}
return dp[n][m];
}
private boolean match(String s, String p, int i, int j) {
if(i == 0) {
return false;
}
if(p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
}
学习到现在，对动态规划有了一定的了解，也能够大概的分析出状态，但是在具体实现过程中仍然存在一定的困难，需要通过题解的帮助才能完成解答。接下来需要逐渐减少对题解的依赖，独立完成动态规划题目的分析和实现。
