接龙数列

考虑最长上升子序列贪心优化思路写法
记max[i]为最后以i结尾的最长接龙串的长度

import java.util.Scanner;

public class Main {
    static final int N = 100010;
    static int[] l = new int[N], r = new int[N], max = new int[12];
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            String num = sc.next();
            int len = num.length();
            l[i] = num.charAt(0) - '0';
            r[i] = num.charAt(len - 1) - '0';
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int left = l[i], right = r[i];
            int t = max[left] + 1;
            ans = Math.max(ans, t);
            max[right] = Math.max(max[right], t);
        }
        System.out.println(n - ans);
    }
}