动态规划算法学习二：最长公共子序列

文章目录

前言
一、问题描述
二、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(i
        return 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);
    }
}