一些算法题解

最长上升公共子序列

最长公共子序列（longest common sequence）：
- 当 $a(x) \neq b(y)$ 时， $f(x, y) = \max(f(x-1, y), f(x, y))$
- 否则： $f(x, y) = f(x-1, y - 1) + 1$
最长上升子序列（longest increasing sequence）：
- 对于 $a(i) < a(k)$ ， $i=1,2,…,k-1$ 时，有 $f(k) = max(1, f(i) + 1)$
- 否则 $f(k) = max(f(k), 1)$

最长上升公共子序列（LICS）：参考LIS，即考虑前面元素的大小情况，参考LCS，考虑子序列的结尾。
- $f(i, j)$ ：只在a序列的前i部分，b序列的前j部分，且以b[j]结尾的LICS的集合。
- 当 $a(i) = b(j)$ ，对任意 $k=0,1,,,j-1$ ，当 $b(k) < b(j) = a(i)$ ，有 $f(i, j) = max(f(i,j), f(i - 1,k) + 1)$ ，否则 $f(i, j) = max(f(i, j), 1)$ 。
- 上一条第 $i$ 层 $j$ 列的结果，依赖于第 $i-1$ 层 $j$ 列之前的所有位置上 $f$ 值的最大值加1，因此可以记录该最大值，当然条件时 $b(k) < a(i)$ 。
- 当 $a(i) \neq b(j)$ 时， $f(i, j) = f(i - 1, j)$ 。

组合数

$C_a^b=\frac{a!}{b!(a-b)!}$

性质：已经选了某一个，剩下 $a-1$ 个里面选 $b-1$ 个；没选这某一个，剩下 $a-1$ 里选 $b$ 个。

$C_a^b = C_{a-1}^b + C_{a-1}^{b-1}$

正则表达式匹配

dp[ i ] [ j ]表示的是 s[0 ~ i] 与 p[0 ~ j] 是否匹配；

p[ j ] != ‘*’ 时 , dp[ i ] [ j ] = dp[ i - 1] [ j - 1] AND (p[ j ] == '.' OR p[ j ] == s[ i ])
p[ j ] == ‘‘时，按照 的重复次数0,1,…,k。有：

$dp(i, j) = dp(i, j - 2) \or \\ (dp(i - 1, j - 2) \and (p_{j-1} == s_i) ) \or \\(dp(i - 2, j - 2) \and (p_{j-1} == s_i) \and (p_{j-1} == s_{i-1})) \or ...$

还有：

$dp(i - 1, j) = dp(i - 1, j - 2) \or \\ (dp(i - 2, j - 2) \and (p_{j-1} == s_{i - 1}) ) \or ...$

由公式：

$(a \and b) \or (b \and c) = （a \or c) \and b$

得：

$dp(i, j) = dp(i, j - 2) \or(dp(i - 1, j) \and (p_{j-1} == s_i))$

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """

        s = " " + s
        p = " " + p
        dp = [[False] * len(p) for _ in range(len(s))]
        dp[0][0] = True
        for i in range(0, len(s)): # 从0开始遍历串，因为存在s为空串且匹配的情况；而p串为空串永远匹配不上
            for j in range(1, len(p)):
                # if (j + 1) < len(p) and p[j + 1] == '*': continue
                if i and p[j] != '*':
                    dp[i][j] = dp[i - 1][j - 1] and (p[j] == '.' or p[j] == s[i])
                elif p[j] == '*':
                    # 
                    dp[i][j] = dp[i][j - 2] or (i and dp[i - 1][j] and 
                    (p[j - 1] == s[i] or p[j - 1] == '.'))
        return dp[len(s) - 1][len(p) - 1]