1. 纯暴力解法
对于一道题而言，我们快速理解题意并进行优化的切入点就是先写出它的暴力解，对于这道题而言，我们可以先尝试写出它的暴力解，思路很明确，就是穷举出两个串的所有子序列，然后两层for比较子序列，遇到相同的就比较长度，从而求出最大长度
public class longestCommonSubsequenceBF {
//求解所有的子序列,其实就是在求子集
//提前加入空集
private List<String> track1 = new LinkedList<>();
private List<String> track2 = new LinkedList<>();
void backtrack(String s, int i,StringBuilder track,List<String> res){
res.add(track.toString());
for(int k = i;k<s.length();k++){
//做出选择
track.append(s.charAt(k));
//递归回溯
backtrack(s,k+1,track,res);
//撤销选择
track.deleteCharAt(track.length()-1);
}
}
public void longestCommonSubsequenceBF(){
String s="abcde";String t="ace";
//然后分别进行子集的求解,子集就是它们的子序列
track1.add("");
track2.add("");
//至此就求出了最大子序列
backtrack(s,0,new StringBuilder(),track1);
backtrack(t,0,new StringBuilder(),track2);
int maxVal = 0;
//然后开始比较其两边的长度
for(int i = 0;i<track1.size();i++){
for(int j = 0;j<track2.size();j++){
if(track1.get(i).equals(track2.get(j))){//是公共的
maxVal = Math.max(maxVal,track1.get(i).length());
}
}
}
System.out.println(maxVal);
}
@Test
public void test(){
longestCommonSubsequenceBF();
}
}这是最纯朴的暴力解法，我们来分析一下时间复杂度,首先，有n个元素，可能产生的子集是2^n个，有两个串，在后面的for-for嵌套中，计算比较次数是2^n * 2^n = 4^n，虽然上面的方法还可以继续优化，但是这样的时间复杂度显然是不可能被接受的，因此需要考其他解法
2. 思路转变
在上面的解法中，我们是直接穷举出了每一种可能，对这每一种可能进行了比较，但是实际上需不需要这样做呢?
首先我们知道，要求最长公共子序列，也就是求从0...n-1之中产生的所有子集中的所有最长子集，而且由于最长的这个性质约定，我们知道，最长的子集肯定是由其更小长度的字符串产生最长子集加上某一个相同字符得来的，因此有一个最优子结构的问题，由于最优子结构互不影响，所以可以采用动态规划的思路来进行求解。
3. 动态规划
对于动态规划而言，我们需要确定三个东西状态、dp数组/函数定义、状态如何转移(选择)
这三步是互相依赖的，只有分析出了前面三个，才有可能对后面的要素进行推导。
好了，首先我们来分析一下状态这一个量。
状态这个量通常是通过我们的暴力解分析来得到的，这也是我们为什么在第一步先写出一个纯暴力解，否则的话状态这个参量比较难以分析确认。
在暴力解中，我们在最终比较的时候，都是基于字符串内容进行的比较，而符合要求的字符串信息有如下特点:字符串内的每一个字符都相同，而这些字符串可以按照一个标准来进行分类，分类其到底是属于哪个区间上的子序列呢?
这个的话可能不太好理解，我们举个例子
a
ab
abc
abcd
abcde
abce
abd
abde
abe
ac
acd
acde
ace
ad
ade
ae
b
bc
bcd
bcde
bce
bd
bde
be
c
cd
cde
ce
d
de
e
a
ac
ace
ae
c
ce
e这个是暴力解中求出的所有子序列，这些子序列的话有一个特点，就是都是从0...i产生的一个去除若干个字符的字符串，那么我们在求解它们是否相同的时候，可以将它们分成i类(0<=i<=n-1)，也就是从0到第i个字符结尾所形成的字符串的子集集合，这个就是状态，因为在推导的过程中这个子集集合是不断变化的。
有了状态之后就可以开始推导dp数组的定义了
根据我们的暴力解可以知道，最终比较的时候，是比较形成的两个字符串的所有子序列是否相同，那么根据我们的状态(从0到i所形成的字符串的子集集合)，就可以进行如下定义
int dp[i][j];
//以s[i-1]结尾的字符串的所有子序列与t[j-1]结尾的字符串的所有子序列所形成的最长公共子序列的长度
//其中1<=i<=n,1<=j<=m然后就是定义base-case，根据dp数组的定义，不难可以知道:当一个串中没有字符的时候，最长公共子序列肯定是0
dp[0][1...m] = 0;
dp[1...n][0] = 0;然后就是最难的一点，如何推导状态转移方程
同理，我们来思考一下如何得到dp[i][j]?
dp[i][j]是以s[i-1]和t[j-1]形成的最长公共子序列的长度
那么我们若干个想要得到s[i-1],t[j-1]，那么路径有:
s[i-1],t[j-2]:这个含义是以s[i-1]结尾形成的字符串的子序列集合与t[j-2]结尾形成的字符串的子序列集合匹配得到的最长公共子序列长度更长
s[i-2],t[j-1]:这个含义是以s[i-2]结尾形成的字符串的子序列集合与t[j-1]结尾形成的字符串的子序列集合匹配得到的最长公共子序列长度更长
s[i-2],t[j-2]+1:这个含义是以s[i-2]结尾形成的字符串的子序列集合与t[j-2]结尾形成的字符串的子序列集合匹配得到的公共子序列长度已经是最长了,但是我目前s[i-1] == t[j-1],因此+1
综上，可以写出状态转移方程
if(s[i-1] == t[j-1]){
dp[i][j] = dp[i-1][j-1] +1;
}else{
dp[i][j] = std::max(dp[i-1][j],dp[i][j-1]);
}4. 代码
class Solution {
public:
static const int N = 1000+10;
int dp[N][N]; //定义dp数组
int longestCommonSubsequence(string s, string t) {
int n = s.length();
int m = t.length();
//base-case
for(int i = 1;i<=n;i++){
dp[i][0] = 0;
}
for(int j = 1;j<=m;j++){
dp[0][j] = 0;
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
if(s[i-1] == t[j-1]){
dp[i][j] = dp[i-1][j-1] +1;
}else{
dp[i][j] = std::max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n][m];
}
};扩展提升
对于子序列的问题,穷举它的所有可能的算法复杂度是指数级的,而子序列的一般问题是求解最长子序列,因为最短子序列就是单个字符,这时候一般都要使用动态规划进行求解。
1. 第一种思路
定义一个一维的
dp数组,在这个思路中,dp数组的定义是在子数组arr[0....i]中,我们要求的子序列(最长递增子序列)的长度是dp[i]
int n = arr.length;
int dp[] = new int[n];
for(int i = 0 ; i < n;i++){
for(int j = 0 ;j < i;j++){
dp[i] = Math.max(dp[i],dp[j]+...)
}
}2.第二种思路
一般来说,尤其是涉及到两个字符串/数组的子序列,一般会使用一个二维的
dp数组对状态和选择进行定义。
int n = arr.length;
int dp[][] = new int[n][n];
for(int i = 0;i < n;i++){
for(int j = 0 ;j < n ;j++){
if(arr[i] == arr[j]){
dp[i][j] = dp[i][j]+1;
}else{
dp[i][j] = 最值(...)
}
}
}涉及到两个字符串/数组的场景,dp数组的定义如下:
在子数组
arr1[0...i]和子数组arr2[0...j],我们要求的子序列的长度为dp[i][j]
涉及到一个字符串/数组的场景,dp数组的定义如下:
在子数组
arr[i...j]中,我们要求的子序列的长度为dp[i][j]
3. 题目实战:最长回文子序列
题面
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。
对于这道题而言,我们知道序列的回文子序列是总问题,那么划分子问题就是回文子序列的子序列,然后递推回到base-case
状态:当前的子序列是哪个?我们可以通过限定指针的位置来获取一个子序列,也就是说
i∈[0,n-1]和j∈[0,n-1],任意的[i,j]都能形成一个子序列，这个子序列在穷举答案的过程中是不断变化的选择:维持原来的子序列的最长回文子序列的长度 or 当有新字符满足条件的时候,更新原来的答案。
dp数组定义:以s[i]字符开头,以s[j]字符结尾的形成的最长回文子序列。状态转移
base-case
//自己和自己就是一个回文子序列
int n = s.length();
int[][] dp = new int[n][n];
for(int i = 0;i<n;i++){
dp[i][i] = 1;
}推广情形
for(int i = 0;i<n;i++){
for(int j = i+1;j<n;j++){
if(s[i] == s[j]){
dp[i][j] = dp[i+1][j-1]+1;
}else{
dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);//子序列之一
}
}
}
