问题描述
对于一个长度为 K 的整数数列：A_1,A_2,\,…,A_K，我们称之为接龙数列当且仅当 A_i 的首位数字恰好等于 A_{i-1} 的末位数字（2\le i\le K）。例如 12,23,35,56,61,11 是接龙数列；12,23,34,56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。
现在给定一个长度为 N 的数列 A_1,A_2,\,…,A_N，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A_1,A_2,\,…,A_N。

输出格式
一个整数代表答案。

样例输入
5
11 121 22 12 2023

样例输出
1

样例说明
删除 22，剩余 11,121,12,2023 是接龙数列。

评测用例规模与约定
对于 20\% 的数据，1\le N\le 20。
对于 50\% 的数据，1\le N\le 10000。
对于 100\% 的数据，1\le N\le 10^5，1\le A_i\le 10^9。所有 A_i 保证不包含前导 0。

题目要求：求计算从中删除多少数能使剩下的序列是接龙序列，换句话说，就是求接龙数列中元素最多的那个一个的元素数量，再用总元素数量减去最多的元素数量即可得到删去最少数的个数。

解题思路

先看数据规模，对于

100\% 的数据，1\le N\le 10^5，1\le A_i\le 10^9

枚举无望，再想想看有没有什么办法，我最开始想的是利用局部最优来使全局最优，也就是贪心算法，但是又仔细想想，贪心算法从头走到尾，如果说总元素最多的接龙数列出现在中间某个位置的时候，这个算法也就失效了，仔细想想，如果把全部等可能的接龙数列都放在一起，元素最多的和元素最小的接龙数列的最后一个元素的尾数一定是从0~9中取得的，那我可以用一个10元素的数组，把尾数分别为0,1,2…9的最多元素的接龙数列存起来，最后再一个个比对选出最大的不就行了?

这就是DP（动态规划）算法的核心思想:

1. 重叠子问题：同一个子问题在求解过程中会被多次使用，通过保存结果避免重复计算。

2. 最优子结构：问题的最优解可以由子问题的最优解递推得到。

动态规划算法的应用

我们设置一个10元素的数组dp，每一个元素有他特别的含义，就比如dp[1]，指的是最优接龙数组最后一个元素中的尾数为1的元素的个数，开始的时候每个元素的值都为0，从给定的数组从头遍历到尾，假如第一个元素为543，分解成头数5,尾数3，那么我们就看看尾数为5，也就是dp[5]的元素个数，它在这里是0，0个元素的接龙序列加上现在这个数那么就是1个元素，此时接龙数组的最后元素的尾数就变成了3，我们就看看dp[3]对应的数，如果说dp[3]指向的那个接龙数组的个数比现在这个接龙数组的个数还大，那么dp[3]不做处理，不然令dp[3]等于现在这个接龙数组，这里dp[3]=0<1,显然令dp[3]=1,接下来的数也是那么操作，形成如下算法:

先看看这个数能接入到哪个接龙数组，接入之后整个数组的元素个数与现存与这个数组最后元素的尾数相同的最大数组的元素个数相比较，如果大于就把之前的数组淘汰掉，如果小于则之前的数组不变。

最后在接龙数组中找到最大元素的那个，读出它的值，总元素的个数减去总值就是减去的最小值

下面是实现代码:

<code>#include <stdio.h>
long long int list[100000];
int dp[10] = {0};//list[i]的值代表着尾数为i的最长接龙数列的元素的个数
int main(void)
{
	long long int n,i;
	scanf("%lld",&n);
	for(i=0;i<n;i++)
	{
		scanf("%lld",&list[i]);
	}
	
	long long int x;
	for(x=0;x<n;x++)
	{
		int front,tail,now;
		front = list[x];
		while(front>=10)
		{
			front/=10;
		}
		tail = list[x]%10;
		now = dp[front] + 1;//这个元素的头数对应的接龙元素的数量加1
		dp[tail] = (now>dp[tail])?now:dp[tail];//如果说原先的那条线路元素更多就没必要改了，否则就改
	}
	long long int max,ans;
	
	max = dp[0];
	for(x=0;x<10;x++)
	{
		max = (dp[x]>max)?dp[x]:max;
	}
	ans = n-max;
	printf("%lld",ans);
	return 0;
	
}</code>