0
已解决
资深光能
线性动规：请问多个序列的最长公共子序列怎么求？（本人太菜，楼下勿喷）
周琪岳在2021-02-02 16:23:20追加了内容
比如输入n个序列
周琪岳在2021-02-02 16:25:00追加了内容
@崔竣恺 @黄子阳 @葛新 @曹灿阳 @汪恺恒 @候平仄 @赵梓超
周琪岳在2021-02-02 16:33:44追加了内容
别给网址
周琪岳在2021-02-04 18:27:04追加了内容
D
0
已采纳
初级守护
我知到怎么写了
0
中级天翼
我自己想的：
先求第1和第2个序列的最长公共子序列，得出的序列再和第三个序列……
还有，你@老师干嘛，酷町喵好久不上线了。
0
资深光能
ding
0
中级天翼
让我们用暴力干掉他（
黄依成在2021-02-02 16:35:29追加了内容
只要数据小一点应该没问题吧
或者尝试用多维数组（？）
0
初级启示者
可以知道两个序列的最长公共序列是一个个对比首尾元素，然后取舍f[i][j]后得出序列（长度）
同理对于多个序列，有两种想法是
1. n次对多个序列的每个元素进行一一比较，若每个序列最大长度有m，则预计时间复杂度
2. 每两个按输入顺序相邻的序列进行求公共子序列，总共求n-1次，若每个序列最大长度为m，则预计时间复杂度
，但对于所有的公共序列组（n-1个），目前不会证明这些序列组的最小值一定是最大子序列长度，或者可以二分法求公共序列（长度），预计时间复杂度
当然以上我说的是求最长公共子序列的长度，如果求最长子序列的元素，那存储就很麻烦了
赵逸凡在2021-02-04 19:05:19追加了内容
听说有一种神仙做法，是先把这些序列进行操作，然后启发式搜索（（（（
@侯平仄 非常厉害，AC了9道非常非常难的省选题，其中有一道是Ynoi！！！他还是小六！！！
