公共子序列问题

最长公共子序列

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/9
'''
给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。

输入格式
第一行包含两个整数N和M。

第二行包含一个长度为N的字符串，表示字符串A。

第三行包含一个长度为M的字符串，表示字符串B。

字符串均由小写字母构成。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N,M≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3
'''
class Solution:
    def maxCommonString(self, A: str, B: str):
        # dp[i][j]表示A[:i]和B[:j] 的最长公共子序列
        # ①A[i] == B[j]: dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j-1]+1)
        # ②A[i] != B[j]: dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
        dp = [[0 for _ in range(len(B)+1)] for _ in range(len(A)+1)]
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if A[i-1] == B[j-1]:
                    dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j - 1] + 1)
                else:
                    dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]

if __name__ == '__main__':
    solution = Solution()
    len_A, len_B = list(map(int, input().split()))
    A = input()
    B = input()
    res = solution.maxCommonString(A, B)
    print(res)

最长上升子序列

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# author：ShidongDu time:2020/4/11
'''
给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数N。

第二行包含N个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤1000，
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
'''
# 状态表示：①集合  所有以a[i]结尾的严格单调上升的子序列    ②属性：max
# 状态计算：根据前一个数是什么情况，一共分成i类：前一个数是a[i-1]，前一个数是a[i-2]...，前一个数是a[0]、前一个数是空

from typing import List
class Solution:
    def upString(self, string: List[int]):
        # dp = [1 for _ in range(len(string)+1)]
        dp = [1] * (len(string)+1)
        for i in range(1, len(dp)-1):
            for j in range(i):
                if string[j] < string[i]:
                    dp[i] = max(dp[j]+1, dp[i])
        return max(dp)

if __name__ == '__main__':
    solution = Solution()
    num = int(input())
    string = list(map(int, input().split()))
    res = solution.upString(string)
    print(res)

最长公共上升子序列

#!usr/bin/env python
# -*- coding:utf-8 -*-
# author: ShidongDu time:2020/7/9
'''
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。

小沐沐说，对于两个数列A和B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过，只要告诉奶牛它的长度就可以了。

数列A和B的长度均不超过3000。

输入格式
第一行包含一个整数N，表示数列A，B的长度。

第二行包含N个整数，表示数列A。

第三行包含N个整数，表示数列B。

输出格式
输出一个整数，表示最长公共上升子序列的长度。

数据范围
1≤N≤3000,序列中的数字均不超过231−1
输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2
'''
# 状态表示：①集合：所有由第一个序列的前i个字母，第二个序列的前j个字母，构成的，且以B[j]结尾的 公共上升子序列   ②属性：max
# 状态计算： 分为两部分：①所有包含A[i]的公共上升子序列  ②所有不包含A[i]的公共上升子序列
# 这样一来，通过转态表示和状态计算，我们就把所有的可能状态模拟出来
# 对于状态计算的 第二部分：即A[i]不在公共上升子序列中，dp[i][j] = max(dp[i][j], dp[i-1][j])
# 对于状态计算的 第一部分：即A[i]在公共上升子序列中，又可以细分为：该公共子序列的倒数第二个数是B[k]
# dp[i][j] = max(dp[i][0], dp[i][1],..., dp[i][k]) for k in range(j) and B[j]>B[k]
from typing import List
class Solution:
    def maxCommonUperString(self, A: List[int], B: List[int]):
        dp = [[0 for _ in range(len(A))] for _ in range(len(B))]
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                dp[i][j] = dp[i-1][j]
                # 对于第二种情况，首先得保证A[i]和B[j]相等
                if A[i-1] == B[j-1]:
                    dp[i][j] = max(dp[i-1][j], 1)
                    for k in range(1, j):
                        if B[j] > B[k]:
                            dp[i][j] = max(dp[i][j], dp[i][k]+1)

        res = 0
        for i in range(len(dp)):
            for j in range(len(dp[0])):
                res = max(res, dp[i][j])
        return res

if __name__ == '__main__':
    solution = Solution()
    num = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = solution.maxCommonUperString(A, B)
    print(res)