Python 高效求解：让数列变身接龙数列最少需删多少数？

以下是解决该问题的Python代码： ```python # 读取输入 n = int(input()) nums = input().split() # dp数组，dp[i]表示以数字i结尾的最长接龙数列的长度 dp = [0] * 10 # 遍历每个数字 for num in nums: # 获取当前数字的首位和末位数字 start_digit = int(num[0]) end_digit = int(num[-1]) # 更新以当前数字末位数字结尾的最长接龙数列长度 dp[end_digit] = max(dp[end_digit], dp[start_digit] + 1) # 找到最长接龙数列的长度 max_length = max(dp) # 计算最少需要删除的数字个数 result = n - max_length # 输出结果 print(result) ``` 代码解释： 1. 读取输入：首先读取整数`n`，表示数列的长度，然后读取`n`个整数并存储在列表`nums`中。 2. 初始化`dp`数组：创建一个长度为10的数组`dp`，`dp[i]`表示以数字`i`结尾的最长接龙数列的长度，初始值都为0。 3. 遍历每个数字：对于每个数字，获取其首位数字`start_digit`和末位数字`end_digit`，更新`dp[end_digit]`的值为`dp[end_digit]`和`dp[start_digit] + 1`中的较大值。 4. 找到最长接龙数列的长度：遍历`dp`数组，找到其中的最大值`max_length`，即最长接龙数列的长度。 5. 计算最少需要删除的数字个数：用数列的总长度`n`减去最长接龙数列的长度`max_length`，得到最少需要删除的数字个数`result`。 6. 输出结果：输出`result`。 复杂度分析： - 时间复杂度：$O(n)$，其中`n`是数列的长度。 - 空间复杂度：$O(1)$，因为`dp`数组的长度是固定的10。 ######[AI问答 | 493点数解答 | 2025-12-13 10:25:59]