最长公共子序列（LCS）-蒲公英云

最长公共子序列（LCS）

problem

leetcode: 1035. 不相交的线

dp[i][j]：nums1[0:i] 和nums2[0:j]的LCS;
如果nums1[i]==nums2[j],则: dp[i][j] = dp[i-1][j-1] + 1,
否则： dp[i][j] = max(dp[i-1][j],dp[i][j-1]).
为了不额外处理边界，记录ans的dp数组整体后移动一位。

code

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        // 两个序列的LCS
        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(nums1[i-1] == nums2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
};

为了看看有没有优化版本，去洛谷找了一个LCS题目做，遇到一个有意思的题目：洛谷：P1439 【模板】最长公共子序列

n高达1e5，这个题直接用 O ( n 2 ) O(n^2) O(n2)的 LCS是过不了的。

再认真读题，两个序列是1-n的排列。

样例：

5 
3 2 1 4 5
1 2 3 4 5

如果第一个序列映射成它的index,即：

3:0, 2:1, 1:2, 4:3, 5:4

则第二个序列根据第一个序列的映射关系，被映射成了：

2 1 0 3 4

两个序列经过映射后变成：

0 1 2 3 4
2 1 0 3 4

我们可以发现映射后第一个序列一定是严格升序的，

此时只需要找映射后第二个子序列的最长上升子序列（LIS），

LIS的长度就是原来两个由1-n排列构成的序列的LCS。

很神奇的将LCS转化成了LIS。

可以使用基于贪心的 O ( N l o g N ) O(NlogN) O(NlogN)解法求解LIS。

code

非c++11 请将unordered_map换成map

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
    int n;
    cin>>n;
    vector<int>A(n);
    vector<int>B(n);
    unordered_map<int,int>mp,num;
    for(int i = 0; i < n; ++i)
    {
        cin>>A[i];
        mp[A[i]] = i;
    }
    for(int j = 0; j < n; ++j)
    {
        cin>>B[j];
        num[j] = mp[B[j]];
    }
    vector<int>st(n+5);
    int k = 0;
    st[0] = -INF;
    // O(nlogn) LIS
    for(int i = 0; i < n; ++i)
    {
        if(num[i]>st[k])
        {
            st[++k] = num[i];
        }
        else
        {
            int l = 1;
            int r = k;
            int pos = -1;
            while(l <= r)
            {
                int mid = l + (r-l)/2;
                if(st[mid]>num[i])
                {
                    pos = mid;
                    r = mid - 1;
                }
                else
                {
                    l = mid + 1;
                }
            }
            if(pos != -1) st[pos] = num[i];
        }
    }
    cout<<k<<endl;
    return 0;
}