＜蓝桥杯软件赛＞零基础备赛20周--第18周--动态规划进阶：从“更小的数”到“接龙数列”

1. 从“更小的数”到“接龙数列”：真题驱动的DP思维跃迁

如果你已经跟着我们的20周备赛计划走到了第18周，并且啃完了上周的“动态规划初步”，那么恭喜你，你已经拿到了算法竞赛世界的一把重要钥匙。上周我们聊了DP是什么、两种编码方法以及基础设计，你可能觉得“哦，DP就是递归加记忆化，或者循环填表”。但理论懂了，面对蓝桥杯真题，比如2023年省赛那道“更小的数”，是不是感觉还是有点无从下手？或者看到“接龙数列”这个题目名字，脑子里一片空白，不知道这和DP有什么关系？

这太正常了。我刚开始学DP的时候也一样，例题都会，换个壳子就懵。关键在于，我们需要完成一次思维的转换：从“学习DP知识点”到“用DP思维拆解真题”。本周，我们就聚焦这个目标。我不会再重复讲斐波那契，而是直接带你钻进去年省赛最热乎的真题里，把“更小的数”和“接龙数列”这两道题，从里到外、从暴力模拟到DP优化，彻底讲透。我的目标很简单：让你看完后，不仅会做这两道题，更能掌握一种“看到题目，如何联想并设计出DP方案”的实战能力。你会发现，DP不是玄学，而是一套有迹可循的“解题流水线”。

2. 真题复盘：“更小的数”的DP降维打击

我们先拿“更小的数”开刀。题目大意是给你一个数字字符串，你可以选择其中一段连续子串进行一次反转，问有多少种选择方案，使得反转后的新数字比原数字小。很多同学的第一反应，也是我当年第一反应，就是暴力模拟：两层循环枚举所有子串的起止点i和j，然后反转，再比较大小。代码写起来很快，思路也直白。

但这就是典型的“模拟思维”，不是“竞赛思维”。我们算笔账：字符串长度n最大是5000。两层循环枚举子串，复杂度是 O(n²)，这大概是2500万级别，看起来还能接受？但别忘了，每次反转和字符串比较（tmp < s）的操作，其本身也是 O(n) 的。所以总复杂度是 O(n³)，在最坏情况下就是1250亿次操作！这绝对会超时，只能过掉小数据量的测试点。我实测过，当n超过1000，程序就卡得不行了。所以，暴力模拟是条死路，我们必须寻找更优解。

这时候，DP就该登场了。我们来回想DP的两个核心特征：重叠子问题和最优子结构。在这道题里，它们存在吗？我们仔细看暴力过程：当我判断子串s[1...5]反转后是否更小时，我需要比较s[1]和s[5]，如果相等，就得去比较s[2]和s[4]。而判断子串s[2...4]时，我又要比较s[2]和s[4]。看到了吗？子问题s[2...4]被重复计算了！这就是“重叠子问题”。而且，大问题s[1...5]的结果，可以直接由小问题s[2...4]的结果推导出来（当首尾字符相等时），这就是“最优子结构”。DP的条件完全满足。

2.1 DP状态设计与转移方程

既然决定用DP，第一步就是设计状态。我们定义dp[i][j]表示：子串s[i...j]反转后，是否比原串小。如果是，dp[i][j] = 1；否则为0。这里i和j是字符串的下标。这个定义非常直观，直接对应了题目的问题。

接下来是关键：状态如何转移？也就是，已知小区间的结果，如何推出大区间的结果？我们分情况讨论子串的首尾字符s[i]和s[j]：

1. 若s[i] > s[j]：反转后，高位（原s[i]）变成了更小的s[j]，整个数肯定变小。所以dp[i][j] = 1。
2. 若s[i] < s[j]：反转后，高位变成了更大的数，整个数肯定变大。所以dp[i][j] = 0。
3. 若s[i] == s[j]：首尾一样，反转后高位和低位没变，那么整个数变大变小，就取决于“剥掉首尾”后的内部子串s[i+1...j-1]反转后的情况。这正是我们定义的状态！所以dp[i][j] = dp[i+1][j-1]。

这个转移方程就是DP解题的灵魂。它完美体现了“大问题化小”的思想。你可能会想，那dp[i+1][j-1]怎么来？这就是DP填表的顺序要解决的问题。

2.2 填表顺序：自底向上的艺术

这是新手最容易栽跟头的地方。你不能直接写个双重循环for i然后for j就开始算。想想看，当i=0, j=8时，我们需要dp[1][7]，但此时dp[1][7]可能还没计算呢！我们必须先算小的，再算大的。

正确的填表顺序，应该按照子串的长度来递推。我们先算所有长度为2的子串（j = i+1），然后算长度为3的（j = i+2），依次类推，直到长度为n。这样，当计算dp[i][j]时，它所依赖的dp[i+1][j-1]对应的是长度更短的子串，肯定已经计算好了。

我们来看核心代码的实现细节。这里以Python为例，因为更清晰：

s = input() n = len(s) dp = [[0] * n for _ in range(n)] # 初始化DP表，所有值为0 ans = 0 # 按照子串长度len遍历，从2到n for length in range(2, n + 1): # 枚举子串的起始位置i for i in range(0, n - length + 1): j = i + length - 1 # 子串的结束位置 if s[i] > s[j]: dp[i][j] = 1 elif s[i] < s[j]: dp[i][j] = 0 else: # s[i] == s[j] # 注意边界：当子串长度仅为2时，i+1 > j-1，我们视作无需反转（相等），结果为0 if i + 1 <= j - 1: dp[i][j] = dp[i + 1][j - 1] else: dp[i][j] = 0 if dp[i][j] == 1: ans += 1 print(ans)

这段代码的复杂度清晰明了：外层循环是长度O(n)，内层循环是起始点O(n)，内部每次操作是O(1)，总复杂度O(n²)。对于n=5000，操作量在2500万级别，现代计算机完全可以在短时间内完成。这就是DP对暴力的“降维打击”：将O(n³)优化到了O(n²)。

2.3 思维对比：为什么DP更快？

我们再深入一层，对比一下两种方法的思维本质。暴力模拟是“独立的”：每个子串的判断都是一个孤立的、从头开始的过程，像一个个散落的点，没有利用任何已知信息。DP则是“关联的”：它通过状态定义和转移方程，把子串之间的关系网络建立了起来。计算长串时，直接复用短串的结果，避免了大量重复的比较操作。这就像你要计算从1加到100，暴力是1+2+3+...+100，而DP（或者说递推）是sum[i] = sum[i-1] + i，后者记住了之前所有的累加结果。这种“记忆”和“复用”，就是DP高效的核心。

3. 举一反三：“接龙数列”的线性DP建模

搞定了“更小的数”，我们趁热打铁，来看2023年省赛B/C组的另一道经典题——“接龙数列”。题目描述大概是：给定一个正整数数列，我们定义“接龙”规则：一个数的最后一位数字，等于下一个数的第一位数字（例如，123的尾是3，345的头是3，它们可以接龙）。现在可以从给定数列中删除一些数，请问最少删除多少个数，可以让剩下的数列构成一个接龙序列？

这道题初看可能不像DP，更像贪心或者模拟。但当你尝试去思考“最少删除”这个最值问题时，DP的嗅觉就应该启动了。因为我们要在众多可能的删除方案中找最优解，这符合DP求解最值问题的场景。

3.1 问题转化与状态定义

直接思考“删多少”有点绕，我们正着想：最少删除，等价于最多保留。我们的目标变成了：从原数列中，找出一个最长的子序列（注意不是连续子串，可以跳着选），使得这个子序列满足接龙规则。那么，最少删除数 = 数列总长度 - 最长接龙子序列长度。

现在，问题转化为了经典的“最长xx子序列”模型，这几乎是线性DP的招牌题型。我们定义状态dp[i]：表示以原数列中第i个数作为结尾的、最长的接龙子序列的长度。注意，这个定义非常重要，它把“结尾”固定了下来，方便我们进行状态转移。

3.2 状态转移与优化

接下来找转移关系。对于第i个数（设其值为num[i]，首位数字为head，末位数字为tail），我们想把它接在某个以第j个数结尾的子序列后面（j < i）。能接上的条件是：num[j]的末位数字等于num[i]的首位数字。

所以，最朴素的转移方程是：dp[i] = max(dp[j] + 1)，对于所有j < i且满足tail[j] == head[i]的j。同时，dp[i]至少为1（只选自己）。然后，我们遍历所有i，找到最大的dp[i]，就是最长接龙子序列的长度。

但是，这样做的复杂度是 O(n²)，n最大10^5的话会超时。需要优化。观察条件tail[j] == head[i]，我们并不关心j具体是哪个，只关心所有以某个特定数字d（0~9）结尾的子序列中，最长的那个长度是多少。因为num[i]只能接在末位是head[i]的序列后面。

于是，我们可以引入一个辅助数组max_len[d]，表示到目前为止，所有以数字d结尾的接龙子序列的最大长度。这样，状态转移可以优化为：

1. 计算当前数字num[i]的head和tail。
2. 以num[i]结尾的最长子序列长度current_len = max_len[head] + 1。因为max_len[head]记录了所有能接在它前面的最佳结果。
3. 用current_len去更新max_len[tail]，因为现在出现了一个以tail结尾的、长度可能更长的子序列。
4. 同时，用current_len更新全局答案ans。

这样，我们只需要遍历一遍数列，每次操作都是 O(1)，总复杂度 O(n)，完美。

3.3 代码实现与细节

n = int(input()) nums = list(map(int, input().split())) max_len = [0] * 10 # 记录以数字0-9结尾的最长子序列长度 ans = 0 for num in nums: # 获取首位和末位数字 tail = num % 10 head = int(str(num)[0]) # 转换为字符串取第一位更稳妥 # 状态转移：当前数字能接在末尾为head的序列后面，形成新的长度 current_len = max_len[head] + 1 # 更新以当前数字末尾tail结尾的最长序列长度 max_len[tail] = max(max_len[tail], current_len) # 更新全局答案 ans = max(ans, current_len) # 最少删除数 = 总长度 - 最长子序列长度 print(n - ans)

这段代码简洁而高效。它背后的DP思想是“状态压缩”，我们把原本需要二维或复杂遍历的状态，压缩到了固定大小（10）的数组中。这提醒我们，在设计DP状态时，要时刻思考哪些信息是必须的，哪些是可以聚合或优化的。“接龙数列”这道题，本质上是一个基于末尾数字分类的最长上升子序列（LIS）变种。掌握它，你就掌握了解决一大类“带约束的最长子序列”问题的钥匙。

4. DP实战精要：从看懂到设计

通过上面两道真题的深度剖析，我们应该跳出具体题目，总结一些可复用的DP实战心法。这些是我在多年刷题和教学中总结的，能帮你更快地识别和设计DP方案。

第一，识别DP的“题感”。当题目出现“最长/最短”、“最多/最少”、“方案数”等求最值或计数关键词，并且数据范围暗示 O(n²) 或更优复杂度时，就要高度怀疑是DP。像“接龙数列”的“最少删除”，就是典型的最值问题。

第二，定义状态是成败关键。dp[i]或者dp[i][j]到底表示什么？常见的套路有：

• dp[i]：以第i个元素结尾的某种最优解（如最长递增子序列）。
• dp[i][j]：涉及两个维度或区间[i, j]的最优解（如“更小的数”，矩阵链乘法）。
• 有时需要增加状态维度，比如dp[i][0/1]表示第i个位置选或不选。 定义状态时，要确保它包含了做出后续决策所需的全部信息，并且能够递推。

第三，寻找状态转移方程。这是最考验思维的一步。问自己：要达到当前状态，上一步可能是什么状态？比如在“更小的数”中，dp[i][j]由dp[i+1][j-1]转移来；在“接龙数列”中，dp[i]（对应current_len）由所有tail[j]==head[i]的dp[j]转移来。多画图，多列举小规模例子，是找到转移方程的不二法门。

第四，确定初始化和计算顺序。这是实现环节最容易出错的地方。像“更小的数”必须按长度递增顺序计算，“接龙数列”的max_len数组初始为0。一定要想清楚，在开始递推前，哪些状态的值是已知的（基础情况），以及先算谁后算谁才能保证需要的子问题已经算好。

第五，空间优化与剪枝。在写出基础DP后，要观察状态转移是否只依赖于有限的上一级状态（如滚动数组），或者像“接龙数列”那样可以压缩状态。同时，对于某些无效状态，可以提前跳过以提升效率。

5. 蓝桥杯DP考点纵览与备赛建议

纵观近几年蓝桥杯省赛，DP是绝对的重头戏，几乎场场必考，而且往往不止一题。考察形式非常灵活：

• 线性DP：这是基础，也是考得最多的。比如最长上升子序列（LIS）模型、最大子段和模型、背包问题变种（虽然蓝桥杯明确背包不多，但思想常见）、路径规划问题（如数字三角形）。“接龙数列”就是线性DP的经典变种。
• 区间DP：像“更小的数”就是典型的区间DP，特征是对一个序列的区间进行操作，状态通常定义为dp[i][j]。石子合并、括号匹配等都是经典模型。
• 状态压缩DP：通常出现在“放置”、“覆盖”类问题中，数据范围较小（如n<=20），用二进制位表示某个位置的状态。这是提高组/国赛的常客，省赛偶尔也会涉及较简单的形式。
• 树形DP：如果题目给的数据结构是树，要求你在树上进行选择或统计，很可能就是树形DP。这需要你先掌握树的遍历。

对于正在备赛的同学，我建议的刷题路径是：线性DP -> 区间DP -> 状态压缩DP/树形DP。先把“更小的数”、“接龙数列”这类真题反复吃透，理解每一步为什么这么做。然后去刷官方练习系统中的历年DP真题，按照题型分类刷。每做一道题，不要只满足于AC，要问自己：这道题的状态定义有没有其他方式？转移方程如何推导？初始化边界是什么？时间空间复杂度能否优化？

我在带学生备赛时发现，很多同学卡就卡在“不敢想”和“不会拆”。看到新题，觉得和做过的题不像，就不敢往DP上想。或者想到了用DP，但不知道怎么定义状态。解决之道就是“模仿”和“练习”。先模仿经典模型的解法，再通过大量练习，把这种“拆解问题、定义状态、寻找转移”的思维过程变成肌肉记忆。记住，DP是一种思维体操，练得越多，你就越熟练。当你再看到一道新题，能下意识地去分析它的子问题结构和最优子性质时，你就真正入门了。剩下的，就是在赛场上稳定发挥，把这份思维力转化为实实在在的分数。