动态规划算法学习二:最长公共子序列
创始人
2024-04-11 11:20:18
0

文章目录

  • 前言
  • 一、问题描述
  • 二、DP实现
    • 1、最优子结构性质*****
    • 2、状态表示*****
    • 3、状态递归方程*****
    • 4、计算最优值*****
    • 5、代码实现:输出最长公共子序列
    • 6、代码实现:输出最优解

前言

一、问题描述

在这里插入图片描述

  • 列举X的所有子序列,然后检查它是否也是Y的子序列,从而确定它是否是X和Y的公共子序列。枚举算法的时间复杂度为指数级时间复杂度。

二、DP实现

1、最优子结构性质*****

在这里插入图片描述
注意: 可能同时有多个长度相等的最长公共子序列!
在这里插入图片描述
倒推—从最后一个元素开始分析

在这里插入图片描述

2、状态表示*****

  1. 输入序列对(X(m-1),Y(n-1) ),(X(m-1),Yn ) 和(Xm,Y(n-1) )都分别表示一个子问题 (xm等于或不等于yn,都可以分解为这三个子问题)

  2. 子问题可以通过两个参数确定,即序列 X 的长度和序列 Y 的长度

  3. C(i,j)表示序列Xi={x1,x2,…,xi }和Yj={y1,y2,…,yj } 的最长公共子序列长度

  4. C(m, n)则表示原问题的最长公共子序列长度

3、状态递归方程*****

  • 当i=0或j=0时,C(i,j)=0;
  • 当i, j>0时,C(i,j)的求解包括 两种情况
    1. xi=yj时, (X(i-1),Y(j-1) )的最长公共子序列末尾添加元素xi (=yj),即可得到(Xi,Yj )的最长公共子序列
    2. xi≠yj时,(Xi,Yj )的最长公共子序列等于(Xi,Y(j-1) )和(X(i-1),Yj )的最长公共子序列的较大者
      在这里插入图片描述

4、计算最优值*****

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
注意:
当第一次遍历 自底向上求解时,X[1] != Y[1],所以走第三条路:求c[0][1] c[1][0]的最大值,但是这两个值都是0,所以取哪一个都可以,所以后续求最长公共子序列的 序列时,这里的左箭头和上箭头都是一样的,

  1. 第一次遍历:

5、代码实现:输出最长公共子序列

代码的输出 就是最长公共子序列的长度

public class Main {public static int MAX = 1000;public static int lcsLength(char[] strX,char[] strY) {int[][] C = new int[MAX][MAX], B = new int[MAX][MAX];int i, j;int m = strX.length + 1;int n = strY.length + 1;for (i = 0; i < m; i++)C[i][0] = 0;  //初始化第一行for (j = 0; j < n; j++)C[0][j] = 0;  //初始化第一列for (i = 1; i < m; i++) {for (j = 1; j < n; j++) {if (strX[i-1] == strY[j-1]) {C[i][j] = C[i-1][j-1] + 1;B[i][j] = 1;} else if(C[i - 1][j] >= C[i][j - 1]) {C[i][j] = C[i-1][j];B[i][j] = 2;} else {C[i][j] = C[i][j-1];B[i][j] = 3;}}// end for(j}//end for(ireturn C[m - 1][n - 1];}public static void main(String[] args) {char[] x = {'A', 'B', 'C', 'B', 'D', 'A', 'B'};char[] y = {'B', 'D', 'C', 'A', 'B', 'A'};int i = lcsLength(x, y);System.out.println(i);}
}

6、代码实现:输出最优解


相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
客厅放八骏马摆件可以吗(家里摆... 今天给各位分享客厅放八骏马摆件可以吗的知识,其中也会对家里摆八骏马摆件好吗进行解释,如果能碰巧解决你...
苏州离哪个飞机场近(苏州离哪个... 本篇文章极速百科小编给大家谈谈苏州离哪个飞机场近,以及苏州离哪个飞机场近点对应的知识点,希望对各位有...