动态规划-最长公共子序列

• 前言
• Java实现
• • 1.Java例题
  • 2.代码运行示例：
• 总结

本博客仅做学习笔记，如有侵权，联系后即刻更改

科普：

• 时间/空间复杂度：
  采用动态规划法求解最长公共子序列时需要引入一个数组C[i,j]用于存储序列X(i)和Y(Jj)的最长公共子序列的长度，算法的时间复杂度为O(mn)，空间复杂度为O(mn)

• 题目描述
  X星人的基因由A、B、C、D、E五种不同的结构组合而成。
  如果两个性别不同的X星人的基因序列相似度大于50%，按照X星的法律他们是禁止结婚的，等于50%据说还是可以的。
  那么基因的相似度怎么计算呢？分别从两个人身上取长度均为N的基因片段，如果它们的最长公共子序列为M，则相似度=M/N。是不是很简单呢？
  现在给你两段X星人的基因序列片段，请你判断他们是不是可以结婚？

• 输入
  每一组测试数据包含3行，
  第1行数字N表示待比较基因序列片段的长度，N<=10^3。
  第2行和第3行为两个长度为N的基因序列片段。
  输入0表示结束。

• 输出
  两个X星人是否可以结婚，如果可以输出”Yes“，如果不可以输出”No“。

• 代码如下：

package oj16;

        import java.util.Scanner;

public class h16 {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    while (scanner.hasNext()) {
      int n = scanner.nextInt();
      if (n == 0) {
        break;
      }
      String[] a = new String[n + 1];
      String[] b = new String[n + 1];
      int[][] c = new int[n + 1][n + 1];

      for (int i = 1; i <= n; i++) {
        a[i] = scanner.next();
      }
      for (int i = 1; i <= n; i++) {
        b[i] = scanner.next();
      }

      lcsLength(a, b, c, n);
      if ((double) c[n][n] / n <= 0.5)
        System.out.println("Yes");
      else System.out.println("No");
    }
    scanner.close();
  }

  static public void lcsLength(String []a,String []b,int [][]c,int n){

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (a[i].equals(b[j]))
          c[i][j] = c[i-1][j-1] + 1;
        else if (c[i-1][j] >= c[i][j-1])
          c[i][j] = c[i-1][j];
        else c[i][j] = c[i][j-1];
      }
    }
  }
}

• 样例输入
  8
  A B C D E A B C
  A C C D C B A E
  6
  A B C D E E
  A E D C B B
  0
• 样例输出
  Yes
  Yes

小小励志

有些事你现在不做，一辈子都不会做了。
如果你想做一件事，全世界都会为你让路。
《搭车去柏林》