
这道题java用动规做超时了,改成c++爆内存,是二维数组的问题吗
import java.io.*;
import java.util.Scanner;
public class AC1 {
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
Scanner scanner = new Scanner(System.in);
int len = scanner.nextInt();
char[] s1 = in.readLine().trim().toCharArray();
char[] s2 = in.readLine().trim().toCharArray();
int[][] dp = new int[len+1][];
for (int i = 0; i < dp.length; i++) {
dp[i] = new int[len+1];
}
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= len; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
}
}
}
System.out.println(dp[len][len]);
}
}
想复杂了,先取B中最后一个从A中最后一个往前找相等,找到记录相等次数,再取B中前一个继续往前找相等,直到A被遍历完,输出n-m,
说一下思路,先从B中取首字母去A中遍历找相等,找到之后取B中的下一个字母从A中的下一个位置继续遍历找相等,如果没有找到就取B中再下一个字母从A中再下一个位置遍历找相等,如果找到,就重复以上动作,统计相等次数并用m记录,
第二次遍历从B中取第二个字母开始去A中遍历,记录和之前遍历较大的相等数
第三次从B中取第三个开始,记录较大相等数,
输出n-m,
先别写代码,用文字语言把步骤定完,再写代码。