Algorithm
本篇文章将从最直观的分治（divide and conquer）角度出发，推导出指数复杂度的DFS解法，再利用记忆化搜索（memoization）减少重复的计算，最终转化为迭代（iterative）的动态规划（dynamic programming）解法。
题目: 写一个程序判断一个正则表达p式是否匹配一个字符串s。
正则表达式由小写字母，星号（'*'）和点（'.'）组成;
' . ' 匹配任意字符
' * ' 匹配任意数量（可以0个）的前一个字符
a-z 匹配字符本身
匹配
s = 'abc', p = 'abc'
s = 'aaaab', p = 'a*b'
s = '', p = 'abc*'
s = 'abcdefg', p = '.*'
不匹配
s = 'abc', p = 'a*'
s = '', p = 'ab*'
分治/ Divide and Conquer
分治做为一种经典和重要的算法设计思路，是很多解题的出发点，练习分治的能力是极其重要的。考虑一般p与s都不为空的情况。从s与p的头观察
● 如果p的第二个字母不是’*’ - 如果p的第一个字母是 ’.’ 那么只要s.substring(1)与p.substring(1)匹配，则s与p匹配。- 如果p的第一个字母是’a’-’z’，那么只要s与p的第一个字母相同，且s.substring(1)与p.substring(1)匹配，s就与p匹配。
● 如果p的第二个字母是’*’，那么如果p去掉头2个字符后能匹配某一个s的后缀，且p的前2个字符能匹配剩下的前缀，则s与p匹配
方法 1 : 分治/深度优先搜索
分治的方法不难理解，但是运行效率较慢。 假设s的长度是n，p的长度是m，最坏情况下每一层recursion会产生O(n)个递归调用，而recursion的深度是O(m)，按照DFS的复杂度分析公式，时间复杂度高达O(n^m)。
方法 2 : 改进分治 在分治的过程中，核心的部分就是induction rule的构建，而对于同一个分治的定义，是可以有不同的induction rule的，不同的induction rule带来的效率也是不同的
对于’*’的情况，我们可以只分成2种情况讨论：匹配空前缀，或者匹配非空前缀。
● 如果’*’匹配空前缀，且s匹配p.substring(2)，则s与p匹配
● 如果’*’匹配非空荐椎，且s.substring(1)匹配p，则s与p匹配
注意第二种情况中的子问题并没有改变p的值，’*’在子问题中保留了下来，可以进一步匹配s.substring(1)的前缀（可为空）。
改进后的分治每一层dfs最多可以产生2个个递归调用，时间复杂度减少到了O(2^m)在Java 7中String.substring的复杂度是O(n)的。注意到dfs的参数始终是最初s与p的某个后缀，我们可以用两个指针表示s和p的后缀的起始点，从而减少不必要的字符串复制。
方法 3 : 记忆化搜索通过观察现有解决方案来找到效率不高的地方，继续利用对常见数据结构和算法的理解进行优化，是系统解决问题的过程中能够体现出的重要能力之一注意到dfs在搜索过程中有可能会对完全一样的参数（相同的子问题）计算多次。对于同样的参数，dfs的计算过程和结果都是完全一致的，所以没有必要做重复的计算。避免重复的计算的方法就是把计算的结果按照dfs的参数存下来，这样以后遇到之前计算过的dfs时可以直接返回上一次的计算结果。
记忆化搜索看似只是小小的优化，但对运行时间却能有巨大的提升。不同子问题的个数总共有O(mn)个，每个子问题只计算一遍。每个子问题的开销不包含任何循环，所以只有O(1)。所以总的时间复杂度变成了O(mn)。记忆化搜索分配了O(nm)的空间，换来的运行时间的提升，是一个空间换时间的策略。 仔细思考不难观察出来，分治法它本质上是在一个图上做一个深度优先搜索，而记忆化搜索本质上是按照这个图的拓扑顺序（topological order）的逆序填表。如果我们能用简单的循环描述出图的拓扑顺序，那么就可以用迭代的形式来完成填表的任务，这就是著名的动态规划。
方法 4 : 动态规划除了递归的方式完成任务，同时我们也能从迭代的角度思考问题，通常迭代的形式复杂度容易分析，运行时间会比递归稍快，但实现难度高
注意到填dp[i][j]的时候，我们可能会用到dp[i][j + 2]， dp[i + 1][j] 和dp[i + 1][j + 1]。由于我们的填表顺序是从下向上，从右向左，所以p[i][j + 2]， dp[i + 1][j] 和dp[i + 1][j + 1]的值一定在dp[i][j]之前填好。动态规划的时间、空间复杂度与记忆化搜索一样，也是O(mn)。 动态规划和记忆化搜索分别从迭代和递归的角度完成了同样的任务。迭代的形式复杂度容易分析，运行时间会比递归形式稍快（递归会有函数调用产生的时间开销），但实现难度较高。推荐初学者从分治、搜索的方法着手。
方法 5 : 动态规划空间优化我们在考察已有解决方案的效率的时候，往往要从两方面去考虑，除了时间之外，大家往往忽视的是对空间的分析和优化动态规划还能否进一步改进呢？答案是肯定的。注意到我们是按照一行一行的顺序填表的，每填一行的时候只需要用到下一行的值。也就是说，其实我们只需要保存最近2行的值就能够完成填表的任务了。
代码实现上我们可以使用'滚动数组'的技巧，数组只声明2行，填的时候用行号除以2的余数做index。这样填表能够自动覆盖不需要的行，最大化的利用空间。空间复杂度从O(nm)减少到O(m)。
经典试题总结：
正则表达式匹配做为一道经典的面试题目，考察的重点在于大家对分治思想的掌握，对于基本的DFS算法的熟练程度和对于动态规划的理解。知其然更要知其所以然，动态规划和DFS等系统的解决问题，其背后考核的是一名合格工程师层层分析优化的思维过程。除此之外，是不是能够准确和正确的处理各种不同的情况，对代码的准确性和可读性的考察在这道题目中也得到了很好的体现。我们不管要解决什么问题，都需要有扎实的算法设计的基本功和系统思维的能力，层层推进来不断在现有解决方案基础上开发更有效率的方法。
图片来自网络，版权属于原作者