LIS最长公共子序列（动态规划与递归的解法博弈）

「爱情、让人受尽委屈。」 2022-05-09 15:04 65阅读 0赞

## 动态规划一 最长公共子序列 ##

考虑假如有如下两个字符串 求其最长的公共子序列
    FRAME
    FAMILY

根据最长公共子序列的定义，显然一眼可以看出最长子串为: FAM

##### 那么要怎么么求呢？怎么用代码实现呢？ #####

在这里首先分析一下求法。  
**比如给字符串一个序号一个串叫A串（FRAME），一个叫B串（FAMILY）**

A串：
    |   F    |    R      |   A       |   M      |   E     |
    B串：
    |   F    |    A      |   M       |   I      |   L     |    Y    |

**首先可以考虑采用递归来解决**

##### step1: 考虑首字符F相等， 那么可以去掉F子序列长度加一 #####

然后问题就变成了求A串（RAME），B串（AMILY）最长子串问题。

A串：
    |    R      |   A       |   M      |   E     |
    B串：
    |    A      |   M       |   I      |   L     |    Y    |

##### step2: 那如果不相等呢? #####

1.  一种方法是继续求A串和B串。**（这里显然是不行的， 因为继续求得结果还是不相等）**
2.  另一种方法就是：去掉A串与B串不相等的首字母（R）  
    *使得问题变为:*

A串：
    |   A       |   M      |   E     |
    B串：
    |    A      |   M       |   I      |   L     |    Y    |

1.  还一种方法就是：去掉B串与A串不相等的首字母（A）  
    *使得问题变为:*

A串：
    |    R      |   A       |   M      |   E     |
    B串：
    |    M      |   I       |   L      |    Y    |

一眼看去并不知道2和3哪种方法求出的结果更好。于是**取其中最大**的那个，即为所求。

> 那到这里问题分析完了， 给代码吧！

/* * 最长公共子序列 */
    public class test_1 { 
    
    	static int 最长公共子序列_递归(String A, String B){ 
    		// 如果有一个字符串长度为0 那么公共子序列长度为0
    		if(A.length() == 0 || B.length() == 0) { 
    			return 0;
    		}
    		if(A.charAt(0) == B.charAt(0)) { // 如果首字符相等
    			// 求解子问题, 主意尾部要加一(字符相等表示为子序列长度加 1)
    			return 最长公共子序列_递归(A.substring(1), B.substring(1)) + 1;
    		}else { // 如果字符不相等
    			// 取2和3其中最大的那个
    			return Math.max(最长公共子序列_递归(A, B.substring(1)), 
    				最长公共子序列_递归(A.substring(1), B));
    		}
    	}
    	public static void main(String[] args) { 
    		// 定义两个字符串
    		String A = "FRAME";
    		String B = "FAMILY";
    		int num = 最长公共子序列_递归(A, B);
    		System.out.println("最长公共子序列长度为:" + num);
    	}
    	
    }

#### 递归时间复杂度 ####

从代码中不难发现此递归的时间复杂度非常的高。**近似于2的N次方**  
而时间复杂度主要来源在于这一行代码。

return Math.max(最长公共子序列_递归(A, B.substring(1)), 
    				最长公共子序列_递归(A.substring(1), B));

我们知道**2的N次方**是一个爆炸性数量级。当A串和B串长度达到10几可能就需要好几秒才能求出。  
**那有没有一种更好的方法呢？**  
其实你再分析上面考虑的几种情况。

1.  当字符相等时
2.  当字符不相等时

假如将两个字符串分别放在一张图的X轴和Y轴上。  
![70][]

1.  当字符相等时剪切A和B时所得的结果（也就是左上角 + 1）即可。
2.  当字符不相等时， 取分别减掉A和减掉B的结果的最大值（左边 和 上边最大值）即可。

**于是可以初始化矩阵为:**  
![70 1][]

> 思想解决了，那么代码就很简单了。  
> 上代码吧！

// 注: 这里就不再写主函数了， 此函数可以直接调用运行
    /** * 求最长公共子序列 - 动态规划算法 * @param str1 A串 * @param str2 B串 * @return */
    	public static int LCS(String str1, String str2) { 
    		// 获取字符串长度
    		int str1Len = str1.length();
    		int str2Len = str2.length();
    		// 创建初始矩阵
    		int myMap[][] = new int[str1Len + 1][str2Len + 1];
    		// 记录最长字符串的来源// 上面为2, 左边为3, 对角为1 
    		int d[][] = new int[str1Len + 1][str2Len + 1];
    		// 开始遍历计算
    		for(int i = 1; i < str1Len + 1; i++) { 
    			for(int j = 1; j < str2Len + 1; j++) { 
    				// 如果两个字符相等, 那么就取上一次匹配加一
    				if(str1.charAt(i - 1) == str2.charAt(j - 1)) { 
    					myMap[i][j] = myMap[i - 1][j - 1] + 1;
    					// 记录路径
    					d[i][j] = 1;
    				}else { 
    					// 否则, 就取剪掉第一个串,与第二个串的最大值计算的
    					if(myMap[i - 1][j] > myMap[i][j - 1]) { 
    						myMap[i][j] = myMap[i - 1][j];
    						d[i][j] = 2;
    					}else { 
    						d[i][j] = 3;
    						myMap[i][j] = myMap[i][j - 1];
    					}
    				}
    			}
    		}
    		/ 计算结束
    		// 输出路径矩阵
    		System.out.println("路径矩阵D为: ");
    		for(int i = 0; i < str1Len + 1; i++) { 
    			for(int j = 0; j < str2Len + 1; j++) { 
    				System.out.print(d[i][j] + " ,");
    			}
    			System.out.println();
    		}
    		// 输出最长子串// 通过路径矩阵可以逆向找出最长子序列是哪几个字符构成的
    		int tFind = 10;
    		int i = str1Len;
    		int j = str2Len;
    		StringBuffer LSCStr = new StringBuffer("");
    		while(tFind != 0) { 
    			tFind = d[i][j];
    			if(tFind == 3) { 
    				// 来源为左边
    				j--;
    			}else if(tFind == 2) { 
    				// 来源为上边
    				i--;
    			}else if(tFind == 1) { 
    				LSCStr.append(str2.charAt(j - 1));
    				i--;
    				j--;
    			}
    		}
    		// 输出最长序列// 由于是逆向构造出的， 所以要翻转一下字符串
    		System.out.println("最大子序列为: " + LSCStr.reverse());
    		System.out.println("最大子序列长度为： " + myMap[str1Len][str2Len]);
    		// 返回最大子序列长度
    		return myMap[str1Len][str2Len];
    	}

#### 动态规划时间复杂度 ####

从代码中不难发现动态规划的时间复杂度相较与递归减小了很多。  
**近似于N\*M**（N为A串长度， M为B串长度）  
而时间复杂度主要来源在于这两行代码。

for(int i = 1; i < str1Len + 1; i++) { 
    			for(int j = 1; j < str2Len + 1; j++) {

#### 空间复杂度 ####

**N\*M**（用了两个二维数组来存放路径来源和结构矩阵。）

**不难看出动态规划能够较好的解决这一问题。**

此文到此结束。谢谢阅读。欢迎评论。

[70]: /images/20220506/3214fc1be70644e39b04902023276665.png
[70 1]: /images/20220506/8a78ff0b292f434692b598724b4528f5.png