20200702：最长公共子序列（leetcode1143）

最长公共子序列

• 题目
• 思路与算法
• 代码实现

题目

思路与算法

1. 本题是很经典的LCS（Longest Common SubSequence）动态规划类的题目，最近开始复习一下这方面的题型。
2. 动态规划可以基本上总结为写出状态转移方程即可。没什么好讲的，我直接贴代码，见详细注释即可。

代码实现

Java实现：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        
        int len1 = text1.length();
        int len2 = text2.length();
        /* 
        初始化dp数组，i,j均从1开始，
        
        dp[i][j]为text1的前i个字符，和text2的前j个字符为输入的LCS值。
        
        动态方程为：
            dp[i][j] = dp[i - 1][j - 1] + 1
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        具体为上面的转移情况还是下面的转移情况其实也很清楚：
            1. 如果这俩子序列中当前遍历的字符相同，很显然此时将当前字符从两个字符串中都去掉得到的LCS只         比当前多的这个字符时的LCS小1，也就是第一个状态转移方程。
            2. 如果不同，那也很简单，不同则需要前移两个字符串之一的指针，要么第一个字符串去掉最后一个，         要么第二个字符串去掉最后一个字符，此时对比他们两者情况下的LCS值，当前情况下的LCS比这两者中大那          个LCS大1，如此即可。
        */

        // 初始化dp数组记得多扩一组，因为dp[0][0]是不存值的。
        int[][] dp = new int[len1 + 1][len2 + 1];
        // 注意我们索引从1开始比较方便些
        for (int i = 1; i <= len1; i++) {
			for (int j = 1; j <= len2; j++) {
				if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
					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[len1][len2];
    }
}
           

C++实现：代码完全相同，注释看Java的

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1=text1.length();
        int len2=text2.length();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(text1[i-1] == text2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[len1][len2];
    }
};