272 最长公共上升子序列

朱雀 2022-09-12 01:54 188阅读 0赞

**1. 问题描述：**

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。小沐沐说，对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。不过，只要告诉奶牛它的长度就可以了。数列 A 和 B 的长度均不超过 3000。

**输入格式**

第一行包含一个整数 N，表示数列 A，B 的长度。第二行包含 N 个整数，表示数列 A。第三行包含 N 个整数，表示数列 B。

**输出格式**

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

**数据范围**

1 ≤ N ≤ 3000，序列中的数字均不超过 2 ^ 31−1。

**输入样例：**

4  
2 2 1 3  
2 1 2 3

**输出样例：**

2  
来源：[https://www.acwing.com/problem/content/274/][https_www.acwing.com_problem_content_274]

**2. 思路分析：**

分析题目可以知道这道题目其实是**最长公共子序列**与**最长上升子序列**的结合，我们可以借助于这两道题目进行状态定义和状态计算，因为涉及到两个序列所以我们需要定义一个二维数组或者二维列表，其中dp\[i\]\[j\]表示所有以第一个序列的前i个数字，第二个序列的前j个数字并且以b\[j\]结尾的最长公共子序列的长度；怎么样进行状态的计算呢？状态计算对应集合的划分，一般是找最后一个不同点，这里我们根据当前的a\[i\]是否包含来划分集合，可以参照下图中的集合划分过程，可以发现当不包含a\[i\]的时候那么dp\[i\]\[j\] = dp\[i - 1\]\[j\]，当包含a\[i\]的时候不好直接计算所以我们需要将左半部分的集合进一步划分（直到划分的集合能够直接计算），划分的依据也是找最后一个不同点，我们可以根据倒数第二个数字是b的哪一个数字进行划分，划分完之后就可以直接枚举计算各个状态的值了。我们可以先写出代码然后再考虑如何优化，代码优化其实是将代码做等价变形，可以发现可以每一次循环的时候可以使用一个maxv变量来存储第一个序列前i个数字和第二个数字前j个数字的最大值即可，这样就可以去除掉一重循环。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_19_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

**暴力（超时）：**

if __name__ == '__main__':
        n = int(input())
        a = [0] + list(map(int, input().split()))
        b = [0] + list(map(int, input().split()))
        dp = [[0] * (n + 1) for i in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i - 1][j]
                # 只有左半部分集合存在的时候才枚举
                if a[i] == b[j]:
                    dp[i][j] = max(dp[i][j], 1)
                    for k in range(1, j):
                        # 判断左半部分集合中划分的集合是否存在
                        if b[k] < b[j]:
                            dp[i][j] = max(dp[i][j], dp[i][k] + 1)
        res = 0
        # 枚举以第一个序列的前n个数字, 第二个序列的前j个数字并且以b[j]结尾的最长公共子序列的长度
        for i in range(1, n + 1):
            res = max(res, dp[n][i])
        print(res)

**优化：**

if __name__ == '__main__':
        n = int(input())
        # 列表前面添加一个0这样会更好处理一点
        a = [0] + list(map(int, input().split()))
        b = [0] + list(map(int, input().split()))
        dp = [[0] * (n + 1) for i in range(n + 1)]
        for i in range(1, n + 1):
            maxv = 1
            for j in range(1, n + 1):
                if a[i] == b[j]:
                    dp[i][j] = max(dp[i][j], maxv)
                else:
                    dp[i][j] = dp[i - 1][j]
                if a[i] > b[j]: maxv = max(maxv, dp[i][j] + 1)
        res = 0
        for i in range(1, n + 1):
            res = max(res, dp[n][i])
        print(res)

[https_www.acwing.com_problem_content_274]: https://www.acwing.com/problem/content/274/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1559a337f7b644ecb07ddb17119f72cd.png