java超难编程题 挑战一下吧 大神帮吗发代码

描述
Alice writes an English composition with a length of N characters. However, her teacher requires that M illegal pairs of characters cannot be adjacent, and if 'ab' cannot be adjacent, 'ba' cannot be adjacent either.

In order to meet the requirements, Alice needs to delete some characters.

Please work out the minimum number of characters that need to be deleted.

输入
The first line contains the length of the composition N.

The second line contains N characters, which make up the composition. Each character belongs to 'a'..'z'.

The third line contains the number of illegal pairs M.

Each of the next M lines contains two characters ch1 and ch2,which cannot be adjacent.

For 20% of the data: 1 ≤ N ≤ 10

For 50% of the data: 1 ≤ N ≤ 1000

For 100% of the data: 1 ≤ N ≤ 100000, M ≤ 200.

输出
One line with an integer indicating the minimum number of characters that need to be deleted.

样例提示
Delete 'a' and 'd'.

自己顶一下 求大神发java代码 或者说思路啊

很简单的题目，你不会做一定是上课没有听。基础知识基本技能还是要掌握的。

一个循环=》 search 查找，找到的话删除返回的索引的那个字符， 循环，完了，

楼上的答案也是神了，注意看题好吧2333
既然要求最少删除次数，那么其实是求这个串中的最长满足条件的子序列长度，用n减去即可。
那么设f(i)表示以第i个位置的字母为首的最长合法子序列长度，f(i)=max(f(j)+1)，其中j为i之后的且满足条件的字符。
因为对每个字母的转移只需要转移到离i最近的位置，故总复杂度为O(26n)。
至于找最近的字符，将每个字母的位置排序，转移的时候顺便移动标记即可。

http://hihocoder.com/discuss/question/3960

感觉这个大神的代码才是靠谱的，好多人题意都理解错了还到处贴代码，也是醉了。。
像这个大神说的，dp[i][j] 表示将前i个字符搞成满足条件的子序列而且最后一个字符是j，最少需要删的个数，这样更新就可以了。到最后把需要删除的最少的个数输出就是正确答案。

解释见代码注释，明白dp表示的啥应该就能理解了
方法一：TLE
import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String str = scanner.next();
int m = scanner.nextInt();
boolean[][] concurrency = new boolean[26][26];
for (int i = 0; i < m; i++) {
String str1 = scanner.next();
concurrency[str1.charAt(0) - 'a'][str1.charAt(1) - 'a'] = true;
concurrency[str1.charAt(1) - 'a'][str1.charAt(0) - 'a'] = true;
}
solve(str, concurrency);
}
public static void solve(String str, boolean[][] concurrency) {
int n = str.length();
int[] dp = new int[n]; // dp[i]表示以i结尾的最长子满足条件子序列的长度
Arrays.fill(dp, 1);
char[] chars = str.toCharArray();
int res = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (!concurrency[chars[i] - 'a'][chars[j] - 'a']) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(dp[i], res);
}
System.out.println(n - res);
}
}

方法二：AC

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String str = scanner.next();
int m = scanner.nextInt();
boolean[][] concurrency = new boolean[26][26];
for (int i = 0; i < m; i++) {
String str1 = scanner.next();
concurrency[str1.charAt(0) - 'a'][str1.charAt(1) - 'a'] = true;
concurrency[str1.charAt(1) - 'a'][str1.charAt(0) - 'a'] = true;
}
solve(str, concurrency);
}
public static void solve(String str, boolean[][] concurrency) {
int n = str.length();
int[][] dp = new int[n][26]; // dp[i][j]表示前i个字符的子串以('a' + j)结尾的最长子序列长度
char[] chars = str.toCharArray();
dp[0][chars[0] - 'a'] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 26; j++) {
dp[i][j] = dp[i - 1][j];
}
int curIndex = chars[i] - 'a';
dp[i][curIndex] = 1;
for (int k = 0; k < 26; k++) {
if (!concurrency[k][curIndex]) {
dp[i][curIndex] = Math.max(dp[i][curIndex], dp[i - 1][k] + 1);
}
}
}
int res = 0;
for (int i = 0; i < 26; i++) {
res = Math.max(res, dp[n - 1][i]);
}
System.out.println(n - res);
}
}