关于算法:算法DP之最长公共子序列

最长公共子序列

1. 问题形容

$ 对于母串 X =<x1,x2,⋯,xm>, Y=<y1,y2,⋯,yn>，求最长公共子序列 $

2. 求解算法

2.1 暴力破解

$ 假如 m <n，对于母串 X，能够找到 2^m- 1 个子序列，而后顺次在母串 Y 中匹配，算法的工夫复杂度会达到指数级 O(n * 2^m)$

2.2 动静布局

最优子结构：
$ 假如 Z =<z1,z2,⋯,zk> 是 XX 与 YY 的 LCS，咱们察看到 $

• $ 如果 xm=yn，则 zk=xm=yn，有 Zk−1 是 Xm−1 与 Yn−1 的 LCS；$
• $ 如果 xm≠yn，则 Zk 是 Xm 与 Yn−1 的 LCS，或者是 Xm−1 与 Yn 的 LCS。$

因而，求解 LCS 的问题则变成递归求解的两个子问题。然而，上述的递归求解的方法中，反复的子问题多，效率低下。改良的方法——用空间换工夫 ，用数组保留中间状态，不便前面的计算, 这就是动静布局（DP) 的核心思想了。
用二维数组 ci 记录串 x1x2⋯xi 与 y1y2⋯yj 的 LCS 长度，则可失去状态转移方程

状态转移方程

JAVA 代码递归实现

public static int lcs(String s1, String s2) {char[][] c = new char[s1.length() + 1][s2.length() + 1];
  for (int i = 1; i <= s1.length(); i++) {c[i][0] = s1.charAt(i - 1);
  }
  for (int j = 1; j <= s2.length(); j++) {c[0][j] = s2.charAt(j - 1);
  }
  return recursion(c, s1.length(), s2.length());
}
public static int recursion(char[][] c, int i, int j) {if (i == 0 || j == 0) {return 0;}
  if (c[i][1] == c[1][j]) {return recursion(c, i - 1, j - 1) + 1;
  } 
  return Math.max(recursion(c, i, j - 1), recursion(c, i - 1, j));
}

JAVA 代码自底向上动静布局实现

public static int lcs(String s1, String s2) {char[][] c = new char[s1.length() + 1][s2.length() + 1];
  int[][] dp = new int[s1.length() + 1][s2.length() + 1];
  // s1,s2 字符串转二维数组
 for (int i = 1; i <= s1.length(); i++) {c[i][0] = s1.charAt(i - 1);
  }
  for (int j = 1; j <= s2.length(); j++) {c[0][j] = s2.charAt(j - 1);
  }
  // 初始化 dp 数组
 for (int i = 0; i <= s1.length(); i++) {dp[i][0] = 0;
  }
  for (int j = 0; j < s2.length(); j++) {dp[0][j] = 0;
  }
  // 填表
 for (int i = 1; i <= s1.length(); i++) {for (int j = 1; j <= s2.length(); j++) {if (c[i][0] == c[0][j]) {dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[s1.length()][s2.length()];
}

参考文献：
【动静布局】最长公共子序列与最长公共子串
动静布局 最长公共子序列 过程图解
动静布局解最长公共子序列(LCS)(附具体填表过程)
《算法导论》第四局部 高级设计和剖析技术