题目 2086: 最长公共子序列

本文主要是介绍题目 2086: 最长公共子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述:

给定两个字符串，寻找这两个字串之间的最长公共子序列。

解题思路:

以二维数组的方式遍历两个字符串，行和列要加一，方便计算，

                       当遍历的两个字符相同时，就代表他两个字符串中都有这个字符，

                       就让这个位置等于左上角的数字加一,dp[i][j] = dp[i-1][j-1] + 1;

                        

                       当两个字符不相等时，让他等于之前记录的公共串，此位置等于，

                      上面和左边两个数中大的那个数，dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);

                             

代码:

package lanqiao;import java.math.BigInteger;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.next();String c = sc.next();int n = s.length() + 1,m = c.length() + 1;int[][] dp = new int[n][m];for(int i = 1;i < n;i ++){for(int j = 1;j < m;j ++){if(s.charAt(i - 1) != c.charAt(j - 1)){dp[i][j] = Math.max(dp[i][j - 1],dp[i - 1][j]);}else{dp[i][j] = dp[i - 1][j - 1] + 1;}}}System.out.println(dp[n - 1][m - 1]);}
}

这篇关于题目 2086: 最长公共子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---