蓝桥杯历届真题 -- 蓝肽子序列

• 题目描述
• 思路
• 代码

tag：动态规划

从样例说明中可以很明显看出这是一个最长公共子序列问题。
最长公共子序列请参考：动态规划基础 - OI Wiki

把每个序列进行拆分，存放到数组中，然后求最长公共子序列。
拆分可以选择使用双指针

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s1 = scan.next(), s2 = scan.next();
        String[] a1 = getArray(s1), a2 = getArray(s2);
        int m = a1.length, n = a2.length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (a1[i - 1].equals(a2[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]);
    }

    private static String[] getArray(String s) {
        int l = 0, r = 0, n = s.length();
        List lst = new ArrayList<>();
        while (r < n) {
            char c = s.charAt(r);
            if (r == l || c >= 'a') r++;
            else if (c <= 'Z') {
                lst.add(s.substring(l, r));
                l = r++;
            }
        }
        lst.add(s.substring(l, r));
        return lst.toArray(new String[0]);
    }
}