一些算法题解

Posted on Edited on In Views:

最长上升公共子序列

  • 最长公共子序列（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)$。

组合数

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

正则表达式匹配

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

  1. p[ j ] != ‘*’ 时 , dp[ i ] [ j ] = dp[ i - 1] [ j - 1] AND (p[ j ] == '.' OR p[ j ] == s[ i ])

  2. p[ j ] == ‘‘时，按照 的重复次数0,1,…,k。有：

还有：

由公式：

得：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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]