题解 | #最长公共子序列(一)#
最长公共子序列(一)
https://www.nowcoder.com/practice/672ab5e541c64e4b9d11f66011059498
总结:
1.由于当截取字符串a从0到i,截取字符串b从0到j,此时两截取的字符串的最长公共子序列与前面的状态有关,并可写出状态转移方程,故使用动态规划可以解决。关键是想出状态转移方程。
dp[i][j]= dp[i−1][j−1]+1, 当text1[i−1]=text2[j−1]时
max(dp[i−1][j],dp[i][j−1]),当text1[i−1]不等于text2[j−1]
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); String[] num = sc.nextLine().split(" "); int m = Integer.parseInt(num[0]); int n = Integer.parseInt(num[1]); String text1 = sc.nextLine(); String text2 = sc.nextLine(); int[][] dp = new int[m+1][n+1]; for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ if(i==0||j==0) dp[i][j]=0; else{ if(text1.charAt(i-1)==text2.charAt(j-1))//由于dp数组i=0j=0空闲,数组dp[i][j]就对应字符串的i-1,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]); } } } System.out.println(dp[m][n]); } }