我们发现，删除最少的数，使他成为接龙数列 等价于
总长-最长接龙数列的长度

55分     最长上升子序列做法一致
l[i]表示第i个数最左边的数字大小
r[i]表示第i个数最右边的数字大小

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int l[N],r[N];
int f[N],g[10];
int main()
{
    int n;
    scanf("%d", &n);
    char nums[20];
    int res = 0;
    for(int i = 1;i <= n;i++)
    {
        scanf("%s",nums);
        l[i] = nums[0]-'0' , r[i] = nums[strlen(nums)-1] - '0';
    }

    for(int i = 1;i <= n;i++)//f[i]表示以第i个数结尾的最长接龙数列
    {
        f[i] = 1;
        for(int j = 1;j < i;j++)
        {
            if(r[j] == l[i])
            {
                f[i] = max(f[i],f[j] + 1);
            }
        }
        res = max(res,f[i]);
    }
    printf("%d",n-res);
}

考虑优化：
第一次循环无法避免，我们必须循环一层O（n）
但是第二次循环可以优化，新开一个数组g[i],用于存储以所有最右边数字等于i的最长接龙数列的长度
f[i]存储的是以第i个数结尾的最长接龙数列的长度

f[i] = max(f[i],g[l[i]] + 1);
g[r[i]] = max(f[i],g[r[i]])

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;

const int N = 100010;
int l[N],r[N];
int f[N],g[10];
signed main()
{
    int n;
    scanf("%d", &n);
    char nums[20];
    int res = 0;
    for(int i = 1;i <= n;i++)
    {
        scanf("%s",nums);
        l[i] = nums[0]-'0' , r[i] = nums[strlen(nums)-1] - '0';
    }

    for(int i = 1;i <= n;i++)//f[i]表示以第i个数结尾的最长接龙数列
    {
        f[i] = 1;
        f[i] = max(f[i],g[l[i]] + 1);
        g[r[i]] = max(g[r[i]],f[i]);//所有r[i]结尾的最长接龙数列长度
        res = max(res,f[i]);
    }
    printf("%d",n-res);
}