精华内容
下载资源
问答
  • 最长公共上升子序列

    千次阅读 2014-08-13 16:04:00
    最长公共上升子序列

      最长公共上升子序列

    问题:

    给定两个字符串x, y, 求它们公共子序列s, 满足si < sj ( 0 <= i < j < |s|).要求S的长度是所有条件序列中长度最长的.

    比较直观的做法(O(n^4))

    可以仿照最长上升子序列用dp[i][j], 表示以xi, yj结束的公共字串的长度.

    so, 我们可以得出递推公式

    if xi != yj
        dp[i][j] = 0
    else
        dp[i][j] = max(dp[ii][ij]) ( 0 <= ii < i, 0 <= ij < j, dp[ii][ij] != 0 && x[ii] < x[i]) + 1
    

    时间复杂是O(n^4)

    O(n^3)的算法

    LICS是从LIS和LCS演变而来的.我们来看看LIS和LCS的动态规划解决方法.

    在LIS中dp[i]表示以xi结束的最长上升子序列的长度.在LCS中dp[i][j]表示x[0…i]和y[0…j]的最长公共字串的长度.

    为什么在LIS中dp[i]表示的不是x[0…i]中的最长子序列的长度?

    因为在算LIS中dp[i]的时, 需要知道上一次字符的信息, 这样才能判断是否把x[i]加入.而在计算LCS中dp[i][j]是不需要知道上一字符的信息, 只考虑当前字符就可以.

    在LICS中, 和LIS中一样, 我们需要知道上一字符的信息, dp[i][j], xi和yj就是上一字符信息, 如果xi, yi 相等, 则信息重复冗余, 我们可以试着消除冗余, 以得到一个更好的算法.

    这样我们可以定义dp[i][j]表示x[0…i]和y[0…j]上的LICS, 并且在y中的结束位置为j.

    so, 我们可以得到递归公式

    if xi != yj
        dp[i][j] = dp[i-1][j]
    else
        dp[i][j] = max(dp[i-1][k])(0 < k < j && y[k] < y[j]) + 1
    

    证明:

    设x[0...m]和y[0...n]上的, 以y[n]为结束字符的最长公共上升子序列为z[0...zn].
    
    若x[m] != y[n], 则显然z[0...zn]为x[0...m-1]和y[0...n]上的, 以y[n]为结束的LICS.
    
    若x[m] == y[n], 则z[0...zn-1]必为x[0...m-1]和y[0...k]上的, 以y[k]为结束的最长的LICS( 0 < k < j), 否则会得出矛盾.
    
        反证:
        设s, s[0...sn]为x[0...m-1]和y[0...k]上的, 以x[k]为结束的一个LICS, 并且sn > zn-1.
    
        那么,s[0...sn] 可以加上y[n], 得到长度sn+1的一个以y[n]为结束字符的最长公共上升子序列, sn+1 > zn, 与假设矛盾.
    
    所以,上述的递推公式的是对的.
    

    时间复杂度为O(n^3).

    O(n^2)对O(n^3)的一个优化.

    我们看到, dp[i][j]依赖于dp[k][j-1] (0 < k < i).

    在计算的时候可以把i作为外层循环,也可以把i作为内层循环.

    如果把i做为外层循环的, 可以做一个优化, 把时间复杂度将为O(n^2).

    O(n^3)的算法

    memset(dp, 0, sizeof(dp));
    for (i = 1; i <= m; i++) {
        for(j = 1; j <= n; j++) {
    
            dp[i][j] = 0;
            if (x[i] != y[j]) {
                dp[i][j] = dp[i-1][j];
            } else {
                for (k = 1; k < j; ++k) {
                    if (dp[i][j] < dp[i - 1][k] && y[k] < y[j]) {
                        dp[i][j] = dp[i - 1][k];
                    }
                }
                dp[i][j] += 1;
            }
    

    如果优化, 就只能优化当x[i] = y[j]的时, dp[i][j]的计算.

    因为现在O(n^2)个子问题,这是怎么搞也搞不掉的.

    看这段代码:

    for (k = 1; k < j; ++k) {
        if (dp[i][j] < dp[i - 1][k] && y[k] < y[j]) {
            dp[i][j] = dp[i - 1][k];
        }
    }
    

    当y[j] = x[i]时, 就等于

    for (k = 1; k < j; ++k) {
        if (dp[i][j] < dp[i - 1][k] && y[k] < x[i]) {
            dp[i][j] = dp[i - 1][k];
        }
    }
    

    这是在求dp[i-1][k] (0 < k < j)中的满足y[k]< x[i]最大值

    因为i是不变的(外层循环), j在递增, 因此没有必要从头计算.

    保存一个mlen变量保存dp[i-1][k] (0 < k < j)中的满足y[k]< x[i]最大值, 当j增加时只用化O(1)的时间更新mlen和计算dp[i][j].

    代码如下:

    for (i = 1; i <= m; i++) {
    
        mlen = 0;
    
        for(j = 1; j <= n; j++) {
    
            dp[i][j] = dp[i-1][j];
    
            //更新mlen
            if (y[j] < x[i] && dp[i - 1][j] > mlen) {
                    mlen = dp[i - 1][j];
            }
    
            //计算dp[i][j]
            if (y[j] == x[i]) {
                dp[i][j] = mlen + 1;
            }
        }
    }
    

    时间复杂度O(n^2)

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    其实仔细想想,在最后的长度应该是:dp [m] [j] ( 0=<j<=n)中的求最大值,而不是在整个二维数组中找最大值,那样的话就浪费时间了!

    练习:

    参考资料:


    展开全文
  • 文章目录最长公共子序列题目描述题解最长上升子序列题目描述题解解法一解法二最长公共上升子序列题目描述题解 最长公共子序列 题目描述 给定两个长度分别为N和M的字符串A和B,求既是A的子序列又是B的子序列的字符串...

    最长公共子序列

    题目描述

    给定两个长度分别为N和M的字符串A和B,求既是A的子序列又是B的子序列的字符串长度最长是多少。
    输入格式
    第一行包含两个整数N和M。
    第二行包含一个长度为N的字符串,表示字符串A。
    第三行包含一个长度为M的字符串,表示字符串B。
    字符串均由小写字母构成。
    输出格式
    输出一个整数,表示最大长度。
    数据范围
    1≤N,M≤1000
    输入样例:
    4 5
    acbd
    abedc
    输出样例:
    3

    题解

    在这里插入图片描述

    状态计算考虑最后一个元素,分别考虑a[i], b[j] 是否在集合中,这里的集合是指既包含在a[1~i]中,又包含在b[1-j]中。0表示在,1表示不在。

    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <string>
    using namespace std;
    const int N = 1010;
    
    int f[N][N];
    char a[N], b[N];
    
    int main()
    {
        int n, m;
        cin >> n >> m;
        
        cin >> a + 1 >> b + 1; //避免下标越界,起始位置从1开始
        
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                if(a[i] != b[j])
                {
                    f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                }
                else
                {
                    f[i][j] = f[i - 1][j - 1] + 1;
                }
            }
        }
        
        cout << f[n][m] << endl;
        
        return 0;
    }
    

    最长上升子序列

    题目描述

    给定一个无序的整数数组,找到其中最长上升子序列的长度。
    示例:
    输入: [10,9,2,5,3,7,101,18]
    输出: 4
    解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

    题解

    在这里插入图片描述

    状态计算考虑最后一个元素,判断在a[1~i]中是否有一个元素a[k]( 0 =< k <= i)小于a[i]
    小于的话就可以转移。

    解法一

     int lengthOfLIS(vector<int>& nums) {
            int n = nums.size();
            vector<int> f(n + 1, 1);
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < i; j++)
                {
                    if(nums[j] < nums[i])
                    {
                        f[i] = max(f[i], f[j] + 1);
                    }
                }
            }
    
    
            int res = 0;
            for(int i = 0; i < n; i++) res = max(f[i], res);
    
            return res;
        }
    

    解法二

    依然是着眼于一个上升子序列的结尾的元素;
    如果已经得到的上升子序列的结尾的数越小,遍历的时候后面接上一个数,就会有更大的可能性构成一个更长的上升子序列;
    既然结尾越小越好,我们可以记录在长度固定的情况下,结尾最小的那个元素的数值,这样定义也是为了方便得到「状态转移方程」。
    为了与之前的状态区分,这里将状态数组命名为 tail。
    定义新状态(特别重要):tail[i] 表示长度为 i + 1 的所有上升子序列的结尾的最小值。

    int lengthOfLIS(vector<int>& nums) {
            int n = nums.size();
            
            if(n < 2) return n;
    
            vector<int> tail; //长度为i的上升子序列末尾元素
    
            tail.push_back(nums[0]);
            int end = 0;
            for(int i = 1; i < n; i++)
            {
                if(nums[i] > tail[end])
                {
                    tail.push_back(nums[i]);
                    end++;
                }
                else
                {
                    int l = 0, r = end;
                    while(l < r)
                    {
                        int mid = l + r >> 1;
                        if(tail[mid] < nums[i]) l = mid + 1;
                        else r = mid;
                    }
    
                    tail[l] = nums[i];
                }
            }
    
            return end + 1;
        }
    

    最长公共上升子序列

    题目描述

    熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
    小沐沐先让奶牛研究了最长上升子序列,再让他们研究了最长公共子序列,现在又让他们研究最长公共上升子序列了。
    小沐沐说,对于两个数列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

    题解

    1.状态表示:
    f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合;
    f[i][j]的值等于该集合的子序列中长度的最大值;
    2.状态计算(对应集合划分):
    首先依据公共子序列中是否包含a[i],将f[i][j]所代表的集合划分成两个不重不漏的子集:
    不包含a[i]的子集,最大值是f[i - 1][j];
    包含a[i]的子集,将这个子集继续划分,依据是子序列的倒数第二个元素在b[]中是哪个数:
    子序列只包含b[j]一个数,长度是1;
    子序列的倒数第二个数是b[1]的集合,最大长度是f[i - 1][1] + 1;

    子序列的倒数第二个数是b[j - 1]的集合,最大长度是f[i - 1][j - 1] + 1;

    算法优化:
    优化第二层循环。因为a[i] == b[j], 第三层循环的作用是求小于b[j]的方案数,也即是求小于a[i]的方案数, 求完一个j后,剩下的j继续往后走变成j+1,但第一层循环i保持不变。即if(b[j + 1] = a[i]), 又会执行第三层循环,这时就会重复求解原来求过的数。

    #include "iostream"
    
    using namespace std;
    
    const int N = 3010;
    
    int f[N][N];
    
    int a[N], b[N];
    
    int main(){
        
        int n;
        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]){
                    int mmax = 1;
                    for(int k = 1; k < j; k++){
                        if(b[k]<b[j]){
                            mmax = max(mmax, f[i-1][k]+1);
                        }
                    }
                    
                    f[i][j] = max(f[i][j], mmax);
                }
            }
        }
        
        //优化后的算法
        /* for(int i = 1; i <= n; i++){
            int mmax = 1;
            for(int j = 1; j <= n; j++){
                f[i][j] = f[i-1][j];
                if(b[j]<a[i]) mmax = max(mmax, f[i-1][j]+1);
                if(a[i] == b[j]) f[i][j] = max(f[i][j], mmax);
                
                }
            }
        */
        
        int res = 0;
        
        for(int i = 1; i <= n; i++) res = max(res, f[n][i]);
        
        printf("%d\n", res);
         
        
        return 0;
    }
    

    链接:https://www.acwing.com/solution/content/4955/

    展开全文
  • 小沐沐先让奶牛研究了最长上升子序列,再让他们研究了最长公共子序列,现在又让他们研究最长公共上升子序列了。 小沐沐说,对于两个数列A和B,如果它们都包含一段位置不一定连续的数,且数值是严格递增的,那么称这...

    熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
    小沐沐先让奶牛研究了最长上升子序列,再让他们研究了最长公共子序列,现在又让他们研究最长公共上升子序列了。
    小沐沐说,对于两个数列A和B,如果它们都包含一段位置不一定连续的数,且数值是严格递增的,那么称这一段数是两个数列的公共上升子序列,而所有的公共上升子序列中最长的就是最长公共上升子序列了。
    奶牛半懂不懂,小沐沐要你来告诉奶牛什么是最长公共上升子序列。
    不过,只要告诉奶牛它的长度就可以了。
    数列A和B的长度均不超过3000。
    输入格式
    第一行包含一个整数N,表示数列A,B的长度。
    第二行包含N个整数,表示数列A。
    第三行包含N个整数,表示数列B。
    输出格式
    输出一个整数,表示最长公共上升子序列的长度。
    数据范围
    1≤N≤30001≤N≤3000,序列中的数字均不超过231−1231−1
    输入样例:
    4
    2 2 1 3
    2 1 2 3

    输出样例:
    2

    朴素版本:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int N = 3010;
    int n;
    int a[N], b[N];
    int f[N][N];
    int main(){
     scanf("%d", &n);
     for (int i = 1; i <= n; i ++)      scanf("%d", &a[i]);
     for (int i = 1; i <= n; i ++)      scanf("%d", &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]){
        int maxv = 1;
        for (int k = 1; k < j; k ++)
         if (a[i] > b[k])
         maxv = max(maxv, f[i - 1][k] + 1);
         f[i][j] = max(f[i][j], maxv);
       }
      }
     }
      int res = 0;
      for (int i = 1; i <= n; i ++)   res = max(res, f[n][i]);
      cout << res << endl;
      return 0;
    } 

    我们发现,maxv其实在计算的时候每次都需要依次枚举,做了重复计算,我们优化只需要在求f[i][j]得同时维护maxv,而因为k小于j,所以我们先求前面的,再优化maxv

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int N = 3010;
    int n;
    int a[N], b[N];
    int f[N][N];
    int main(){
     scanf("%d", &n);
     for (int i = 1; i <= n; i ++)      scanf("%d", &a[i]);
     for (int i = 1; i <= n; i ++)      scanf("%d", &b[i]);
       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 (a[i] > b[j])   maxv = max(maxv, f[i - 1][j] + 1);
      }
     }
      int res = 0;
     for (int i = 1; i <= n; i ++)   res = max(res, f[n][i]);
      cout << res << endl;
      return 0;
    }

    参考文献:AcWing:yxc

    展开全文
  • 272. 最长公共上升子序列 ①. 题目②. 思路③. 学习点④. 代码实现 原题链接 ①. 题目 ②. 思路 f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合; f[i][j]的值等于该集合的子序列中长度...

    原题链接

    ①. 题目

    在这里插入图片描述

    ②. 思路

    在这里插入图片描述

    • f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合;
    • f[i][j]的值等于该集合的子序列中长度的最大值;
    • 不包含a[i]的子集,最大值是f[i - 1][j]
    • 包含a[i]的子集,将这个子集继续划分,依据是子序列的倒数第二个元素在b[]中是哪个数:
      子序列只包含b[j]一个数,长度是1;
      子序列的倒数第二个数是b[1]的集合,最大长度是f[i - 1][1] + 1

      子序列的倒数第二个数是b[j - 1]的集合,最大长度是f[i - 1][j - 1] + 1

    ③. 学习点

    最长上升子序列 | 最长公共子序列的

    ④. 代码实现

    import java.util.Scanner;
    
    public class _272_最长公共上升子序列 {
    	static int N=3010;
    	static int[] a=new int[N];
    	static int[] b=new int[N];
    	static int[][] f=new int[N][N];
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();
    		for (int i =1; i <=n; i++) {
    			a[i]=sc.nextInt();
    		}
    		for (int i =1; i <=n; i++) {
    			b[i]=sc.nextInt();
    		}
    		
    		for (int i =1; i <=n; i++) {
    			for (int j =1; j <=n; j++) {
    				//所有不包含a[i]的公共子序列
    				f[i][j]=f[i-1][j];
    				//所有包含a[i]的公共子序列 ,一定有 a[i]==b[i]
    				if(a[i]==b[j]) {
    					f[i][j]=1;
    					//最长子序列的定义
    					for (int k = 1; k <j; k++) {
    						if(b[k]<b[j]) {
    							f[i][j]=Math.max(f[i][j], f[i-1][k]+1);
    						}
    					}
    				}
    			}
    		}
    		int res=0;
    		//以b[j]结尾的公共上升子序列,遍历求出最大值
    		for (int i =1; i <=n; i++) {
    			res=Math.max(res, f[n][i]);
    		}
    		System.out.println(res);
    	}
    }
    

    在这里插入图片描述

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,685
精华内容 2,274
关键字:

最长公共上升子序列