题目描述
对于一个长度为 K 的整数数列：A1,A2,…,AK，我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字（2≤i≤K）。
例如 12,23,35,56,61,11 是接龙数列；12,23,34,56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。
现在给定一个长度为 N 的数列 A1,A2,…,AN，请你计算最少从中删除多少 个数，可以使剩下的序列是接龙序列？
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,…,AN。
输出格式
一个整数代表答案。
输入输出样例
输入
5 11 121 22 12 2023输出
1
说明/提示
【样例说明】
删除 22，剩余 11,121,12,2023 是接龙数列。
【评测用例规模与约定】
对于 20% 的数据，1≤N≤20。
对于 50% 的数据，1≤N≤104。
对于 100% 的数据，1≤N≤105，1≤Ai≤109。所有 Ai 保证不包含前导 0。
蓝桥杯 2023 省赛 B 组 E 题。
P9242 [蓝桥杯 2023 省 B] 接龙数列 - 洛谷
题目及思路：遇到最值问题我们可以往动态规划上思考，题目说要求最少删除多少个数后能形成最长接龙序列，所以说我们可以转换一下，求出最长接龙序列，然后总数n-最长接龙序列=最少删除个数。就比如样例中，总数n=5，然后求最长接龙序列，求出的最长接龙序列为4，所以5-4=1，即为最少删除个数1后能形成最长接龙序列。那所以我们如何来求最长接龙序列呢？
动规五部曲（dp含义、递推公式、初始化、遍历顺序、打印数组） ，主要的就是把大问题拆解成小问题，小问题的值保存下来，从小问题的答案推导到最终答案，空间换时间。
dp含义： dp[last] 表示以 last 结尾的最长接龙序列长度
一开始我看着有点像最长递增子序列（LIS），都是要找一个满足某种条件的最长子序列。如果按照传统的LIS思路，定义dp[i]表示以第i个数结尾的最长接龙序列长度，那么对于每个i，需要遍历前面所有的j，找到满足条件的j，然后更新dp[i]。这样的话时间复杂度还是O(N²)，显然不行。所以必须得想办法优化状态转移的过程。
那为什么要这样定义呢？接龙数列的核心规则是：
当前数的首位必须等于前一个数的末位。
这意味着，每个数的作用完全由其 首位（s） 和 末位（e） 决定，与数值本身无关。
所以利用末位数字只有 0~9 的特点，将状态维度压缩到 10，使得时间复杂度为 O(N)。
我们可以数组dp[last]，其中dp[last]表示以数字d结尾的最长接龙序列的长度。比如，dp[3]表示当前所有以3结尾的序列中最长的那个的长度。对于当前处理的数num，它的首位是s，末位是e。那么这个数可以接在所有以s结尾的序列后面，形成一个新的以e结尾的序列，新的长度就是dp[s] + 1。然后我们需要比较这个新的长度是否比当前的last[e]大，如果更大，就更新last[e]。再比如当前num首位为3，末位为7，这时候我们要形成接龙序列，则是看与首位3相同的前面的末尾也是3的数，而在此之前，我们每次记录的都是以数字d结尾的最长接龙序列的长度，与dp[3]相关，dp[3]等于多少则是说明当前数能与前面形成接龙序列长度就为多少再加1，然而末位是7，所以形成的最新接龙序列长度为dp[7] = dp[3] +1。（13，32，23，37）
举个例子，比如输入数列是11,121,22,12,2023。第一个数11的首位和末位都是1，所以last[1]会被更新为1。第二个数121的首位是1，末位是1，所以它可以接在last[1]=1后面，形成长度为2的序列，更新last[1]为2。第三个数22的首位是2，末位是2，此时last[2]初始为0，所以它自己作为一个新序列，长度1，更新last[2]为1。第四个数12的首位是1，末位是2，此时last[1]=2，所以新长度是3，更新last[2]为3。最后一个数2023的首位是2，末位是3，此时last[2]=3，所以新长度是4，更新last[3]为4。最终最长序列长度是4，总长度5，所以需要删除1个数。
所以进一步得出递推公式：
对于每个数 num，假设其首位为 s，末位为 e：
-
如果
num能接在某个以s结尾的序列后，则新序列长度为dp[s] + 1。 -
如果这个新长度比当前记录的
dp[e]更长，则更新 dp[e]。
公式表达：
dp[e]=max(dp[e],dp[s]+1)
初始化
-
初始时，所有
last[d]均为0，表示没有任何序列。 -
当处理第一个数时，其自身形成长度为
1的序列，更新last[e] = 1。
遍历顺序：从前往后
打印数组：当遇到疑惑或者提交错误时，打印数组出来比较快速的看看哪一步有错。
以下是我c语言代码仅供参考：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<limits.h>
#include<stdlib.h>
#include<math.h>
#include <stdbool.h>// 获取数字的首位
int get_first_digit(int num)
{while (num >= 10) {num /= 10;}return num;
}int main()
{int max_len = 0;int n;scanf("%d", &n);// dp[last] 表示以 last 结尾的最长接龙序列长度int dp[10] = { 0 }; // 末位数字只能是 0~9，所以数组大小是10for (int i = 0; i < n; i++){int num;scanf("%d", &num); // 计算当前数字的首位和末位int s = get_first_digit(num);int e = num % 10;dp[e] = dp[e] > dp[s] + 1 ? dp[e] : dp[s] + 1;// 更新最长的接龙序列长度if (dp[e] > max_len) {max_len = dp[e];}}// 最少需要删除的数的个数 = 总长度 - 最长序列长度printf("%d\n", n - max_len);return 0;
}
