第一个点WA
查看原帖
第一个点WA
1289839
ICPC42楼主2024/4/1 10:16

求问,为什么第一个点WA了?

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int n = s.length();

        // 法1:自身翻转后求 LCS

        // 法2:区间DP
        int[][] dp = new int[n][n]; // dp[i][j] 表示子串 [i, j] 中最长回文子序列的长度
        for (int i = 0; i < n - 1; i++) {
            dp[i][i] = 1;
        }
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = 2;
            }
        }
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 2);
                }
            }
        }

        System.out.println(n - dp[0][n - 1]);
        scanner.close();
    }
}
2024/4/1 10:16
加载中...