请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
解题思路：
因此，本题的状态共有 m×n 种，应定义状态矩阵 dp ，dp[i][j] 代表 s[:i] 与 p[:j] 是否可以匹配。
做好状态定义，接下来就是根据 「普通字符」 , 「.」 , 「*」三种字符的功能定义，分析出动态规划的转移方程。
动态规划解析：
复杂度分析：
时间复杂度 O(MN) ： 其中 M,N 分别为 s 和 p 的长度，状态转移需遍历整个 dp 矩阵。
空间复杂度 O(MN) ： 状态矩阵 dp 使用 O(MN) 的额外空间
class Solution{ public boolean isMatch(String s,String p){ int m = s.length()+1,n = p.length()+1; boolean dp[][] = new boolean[m][n]; dp[0][0] = true; // 初始化首行 for(int j=2;j<n;j+=2){ dp[0][j] = dp[0][j-2]&&p.charAt(j-1)=='*'; } // 状态转移 for(int i=1;i<m;i++) { for (int j = 1; j < n; j++) { if (p.charAt(j - 1) == '*') { if(dp[i][j-2]) dp[i][j] = true;//1. else if(dp[i-1][j]&&s.charAt(i-1)==p.charAt(j-2)) dp[i][j] = true;//2. else if(dp[i-1][j]&&p.charAt(j-2)=='.') dp[i][j] = true;//3. }else{ if(dp[i-1][j-1]&&s.charAt(i-1)==p.charAt(j-1)) dp[i][j]=true;//1. else if(dp[i-1][j-1]&&p.charAt(j-1)=='.') dp[i][j] = true;//2. } } } return dp[m-1][n-1]; } }
dp五部曲:
1.状态定义（确定dp数组及其下标含义）:dp[i]为长度为i的绳子剪成m段最大乘积为dp[i]
2.状态转移（确定递推公式）:dp[i]有两种途径可以转移得到
2.1 由前一个dp[j]*(i-j)得到,即前面剪了>=2段,后面再剪一段,此时的乘积个数>=3个
2.2 前面单独成一段,后面剩下的单独成一段,乘积为j*(i-j),乘积个数为2
两种情况中取大的值作为dp[i]的值,同时应该遍历所有j,j∈[1,i-1],取最大值
3.初始化（dp数组初始化）:初始化dp[1]=1即可
4.遍历顺序:显然为正序遍历
5.返回坐标:返回dp[n]