解题思路:
以二维数组的方式遍历两个字符串,行和列要加一,方便计算,
当遍历的两个字符相同时,就代表他两个字符串中都有这个字符,
就让这个位置等于左上角的数字加一,dp[i][j] = dp[i-1][j-1] + 1;
当两个字符不相等时,让他等于之前记录的公共串,此位置等于,
上面和左边两个数中大的那个数,dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
最后输出二维数组的最后一位就可以了。
// 动态转移方程式为
if ar[i] != ar[j] dp[i][j] = Math.max(dp[i][j-1],dp[i-][j])
else dp[i][j] = dp[i-1][j-1] + 1;
// 在题目里面就是
if (s.charAt(i-1) != t.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;
}
注意事项:
主要要搞懂状态转移方程式,理解了就很简单,然后代入编程里面实现就好了
参考代码:
import java.util.Scanner; public class Mian{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); String t = sc.next(); int n = s.length()+1,m = t.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) != t.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]); } }
0.0分
4 人评分
K-进制数 (C++代码)浏览:859 |
C二级辅导-计负均正 (C语言代码)浏览:658 |
母牛的故事 (C语言代码)浏览:435 |
WU-蓝桥杯算法提高VIP-勾股数 (C++代码)浏览:1607 |
分糖果 (C语言代码)浏览:920 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:686 |
C语言程序设计教程(第三版)课后习题9.2 (C语言代码)浏览:612 |
回文数(一) (C语言代码)浏览:1120 |
C二级辅导-公约公倍 (C语言代码)浏览:665 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:542 |