当前位置:网站首页>Dynamic programming the longest common ascending subsequence-n ^ 2 solution

Dynamic programming the longest common ascending subsequence-n ^ 2 solution

2021-03-26 03:22:13 Kocoder

1. Title Description

Given two sequences \(A, B\), If they all contain a number whose position is not necessarily continuous , And the value is strictly increasing , Then we call this segment a common ascending subsequence of two sequences . seek \(A\) and \(B\) The longest common ascending subsequence of .

Input format

The first line contains an integer \(N\), Express \(A\) and \(B\) The length of .

The second line contains \(N\) It's an integer , Represents a sequence of numbers \(A\).

The third line contains \(N\) It's an integer , Represents a sequence of numbers \(B\).

Output format

Output an integer , Represents the length of the longest common ascending subsequence .

Data range

\(1 ≤ N≤ 3000\), No number in the sequence exceeds \(2^{31} - 1\).

sample input

4
2 2 1 3
2 1 2 3

sample output

2

2. Simple solution \(O(n^3)\)

The naive solution combines the longest common subsequence with the longest ascending subsequence model .

use \(f[i][j]\) Represents the front of the first sequence \(i\) Number , And the front of the second sequence \(j\) Number , And the last number is \(b[j]\) The length of the longest common ascending subsequence of .

According to \(a[i]\) Is it equal to \(b[j]\) Have a classified discussion .

\[f[i][j]=\left\{ \begin{array}{rcl} f[i - 1][j] & & {a[i] != a[j]}\\ max_{k < j And b[k] < b[j]}(f[i][j], f[i- 1][k]) & & {a[i] == b[j] }\\ \end{array} \right. \]

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 3010;
int a[N], b[N];
int n;
int f[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            f[i][j] = f[i - 1][j];
            if(a[i] == b[j])
            {
                f[i][j] = max(f[i][j], 1);
                for(int k = 1; k < j; k ++)
                    if(b[k] < b[j]) f[i][j] = max(f[i][j], f[i - 1][k] + 1);
            }
        }
    }
    int res = 0;
    for(int i = 1;i <= n; i ++) res = max(res, f[n][i]);
    cout << res << endl;
    return 0;
}

3. Code optimization \(O(n^2)\)

The time complexity of the above simple method is \(O(n^3)\). So how do we optimize ?

  • Look at the innermost loop of the code

     if(a[i] == b[j])
     {
         f[i][j] = max(f[i][j], 1);
         for(int k = 1; k < j; k ++)
             if(b[k] < b[j]) f[i][j] = max(f[i][j], f[i - 1][k] + 1);
     }
    

    Because when you execute the innermost loop a[i] == b[j]. So the innermost condition can be changed to b[k] < a[i].

  • Consider the whole cycle

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            f[i][j] = f[i - 1][j];
            if(a[i] == b[j])
            {
                f[i][j] = max(f[i][j], 1);
                for(int k = 1; k < j; k ++)
                    if(b[k] < a[i]) f[i][j] = max(f[i][j], f[i - 1][k] + 1);
            }
        }
    }
    

    We're actually asking for : When the first cycle comes to i, The second cycle goes to j And meet " a[i] > b[k] And k < j " when f[i - 1][j] The maximum of .

    That is to say, when we visit the second j When the layers loop , Before need j-1 Layer data . therefore , Can be in j In the loop of .

    The code is as follows

    for(int i = 1; i <= n; i ++)
    {
        int maxv = 1;
        for(int j = 1; j <= n; j ++)
        {
            f[i][j] = f[i - 1][j];
            if(a[i] == b[j]) f[i][j] = max(f[i][j],maxv);  
            if(b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);  // maxv The update of must be in f[i][j] After the update of .
        }
    }
    

4. summary

  • This problem is a combination of the longest common subsequence model and the longest ascending subsequence model , We can use Longest ascending subsequence And the longest common subsequence , State representation and state transition equation are constructed .
  • The time complexity of the naive solution is high , But we can optimize according to the code , The complexity of time is determined by \(O(n^3)\) drop to \(O(n^2)\).

版权声明
本文为[Kocoder]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/03/20210311213904136k.html