1. 项目概述从“修路”到线性DP的思维跃迁最近在复盘蓝桥杯2022年国赛的真题其中一道名为“修路”的题目让我印象尤为深刻。这道题初看像是一道普通的模拟或者贪心题但仔细分析后会发现它是一道非常经典的线性动态规划Linear DP问题。很多同学在竞赛中看到“修路”、“铺砖”这类场景第一反应可能是去模拟施工过程结果要么代码冗长复杂要么根本无法在规定时间内求解。实际上这类问题往往考察的是我们能否将现实场景抽象为数学模型并运用高效的算法思想去解决。今天我就来彻底拆解这道“修路”题不仅给出答案更重要的是分享如何识别DP问题、如何构建状态转移方程以及如何优化代码实现。无论你是正在备赛蓝桥杯还是想巩固DP算法这篇文章都将带你走一遍完整的解题心路历程。这道题的核心是给定一条道路和若干种不同长度的砖块要求用这些砖块铺满道路且相邻砖块必须满足特定条件例如长度之和为质数或者满足某种差值关系具体以题目描述为准。我们需要计算有多少种不同的铺设方案。这立刻排除了暴力枚举的可能性因为道路长度和砖块种类稍大方案数就会呈指数级增长。此时动态规划“以空间换时间”、“记录子问题最优解”的思想就成了唯一的出路。我们将道路的每一个位置看作一个“状态”而铺设砖块的过程就是“状态转移”。接下来我们就一步步拆解这个思维过程。2. 核心需求解析与问题抽象要解决任何DP问题第一步也是最关键的一步就是问题抽象。我们不能被“修路”、“砖块”这些具体的表象迷惑必须提炼出背后的数学模型。2.1 题目要素提取首先我们需要明确题目给出的所有条件通常包括道路总长度n这是我们需要覆盖的总目标通常是一个整数。砖块类型每种砖块有一个特定的长度如长度为1、2、3的砖。题目可能会直接给出一个砖块长度数组blocks[]。铺设规则这是题目的核心约束决定了状态如何转移。在2022年国赛题中规则是“相邻两块砖的长度之和必须为质数”。这是一个典型的状态转移约束条件。所求目标通常是求铺满长度为n的道路的方案总数。答案可能需要对一个大数取模如1e97这是竞赛题的常规操作防止答案过大。2.2 抽象为DP模型基于以上要素我们可以进行抽象状态定义我们定义dp[i][last]表示一个状态。其中i表示当前已经铺设的道路长度。这是线性DP中最常见的维度代表了进程。last表示最后一块铺设的砖的类型或长度。这是解决“相邻约束”问题的关键因为下一块砖的选择只和当前最后一块砖有关这就是无后效性的体现。last这个维度我们称之为“状态维度”它携带了影响后续决策的历史信息。所求答案最终答案是当铺设总长度i等于道路总长n时所有可能的last状态对应的方案数之和即sum(dp[n][last])。状态转移假设当前状态是dp[i][last]它表示铺设了长度i且最后一块砖是last的方案数。我们要铺设下一块砖设其长度为block。那么转移能否发生取决于last和block是否满足“相邻砖块长度之和为质数”这个条件。如果满足那么状态dp[iblock][block]就可以从dp[i][last]转移过来并且方案数增加dp[i][last]。通过这样的抽象一个具体的工程问题就变成了一个清晰的、可计算的二维表格填充问题。我们的任务就是正确地初始化这个表格并按照逻辑填充它。3. 动态规划思路详解与状态设计理解了问题抽象后我们来深入探讨DP的核心——状态设计。状态设计的好坏直接决定了算法的效率和代码的复杂度。3.1 为什么是二维状态dp[i][last]这是本题最精妙的地方。如果我们只定义dp[i]表示铺满长度i的方案总数那么在状态转移时我们会遇到一个致命问题当我们想从dp[i]转移到dp[iblock]时我们无法判断新加的这块block砖是否和“前一块砖”即构成dp[i]方案的最后一块砖满足相邻条件。因为我们丢失了“最后一块砖是什么”这个关键信息。因此我们必须增加一个状态维度last来记录这个信息。这样dp[i][last]就精确地描述了一个“子问题”所有铺了长度i并且以last类型砖结尾的铺设方案集合。这个集合的方案数就是dp[i][last]的值。3.2 状态转移方程推导有了状态定义转移方程就呼之欲出了。我们采用“当前状态贡献给未来状态”的思考方式也称为“刷表法”。对于每一个当前状态(i, last)遍历所有可能的下一块砖block。检查约束条件last上一块砖与block下一块砖的长度之和是否为质数。如果条件满足说明我们可以从当前状态(i, last)通过再铺一块block砖到达一个新的未来状态(iblock, block)。那么未来状态(iblock, block)的方案数就应该加上当前状态(i, last)所拥有的所有方案数。因为当前状态的每一种方案都可以通过追加一块block砖生成一种新的、到达未来状态的方案。用数学公式表达就是dp[iblock][block] dp[i][last]其中(last block)是质数。注意这里有一个非常重要的细节就是iblock不能超过道路总长度n。在编程时我们需要先判断iblock n再进行转移。3.3 初始化与边界处理DP的初始化是解决问题的起点必须小心处理。初始状态dp[0][?]当铺设长度为0时我们一块砖都没铺。那么“最后一块砖”是什么这是一个虚拟的状态。通常我们引入一个“起点”或“虚拟砖”的概念。我们可以定义last0表示还没有铺任何砖或者理解为从起点开始铺。那么dp[0][0] 1表示“长度为0且最后一块砖为虚拟砖无砖”的状态有1种方案即空方案。另一种常见的初始化方法是将第一块砖的铺设作为初始化。即遍历所有砖块block如果从起点开始铺这块砖是合法的有时起点有特殊约束本题中起点铺任何砖都合法因为没有前一块砖与之相邻则dp[block][block] 1。两种方法等价但第一种使用虚拟起点在代码上通常更统一、更简洁。4. 算法实现与代码精讲理论清晰后我们来看代码实现。这里我会提供两种风格的代码一种是便于理解的朴素版本另一种是进行了空间优化的滚动数组版本。4.1 基础版本代码实现首先我们需要一个判断质数的工具函数。由于题目中砖块长度不会太大通常不超过1000我们可以用简单的试除法或者预先用埃拉托斯特尼筛法埃氏筛打一个质数表这样在转移时可以用O(1)时间判断。def is_prime(num: int) - bool: 判断一个数是否为质数简单试除法适用于num不大时 if num 2: return False i 2 while i * i num: if num % i 0: return False i 1 return True def solve_road_construction(n, blocks): 解决修路问题的基础DP版本 Args: n: 道路总长度 blocks: 砖块长度列表 Returns: 铺满道路的方案总数对 MOD 取模 MOD 10**9 7 # 砖块种类数 m len(blocks) # dp[i][last] 初始化一个 (n1) x (max_block1) 的数组last维度取砖块最大长度1包含虚拟的0 max_block max(blocks) # 注意last索引需要能表示所有砖块长度以及虚拟的0。所以维度是 max_block1 # 但更精确的做法是last的维度是 max_block1但转移时只用到blocks中存在的长度。 # 为了清晰我们可以用字典或者将last维度设为 max_block1但只处理有效的last。 # 这里采用二维列表last维度大小为 max_block1 dp [[0] * (max_block 1) for _ in range(n 1)] # 初始化长度为0最后一块砖为虚拟砖(0)的方案数为1 dp[0][0] 1 # 状态转移遍历所有已铺设长度i for i in range(n 1): # i从0到n # 遍历所有可能的最后一块砖类型last # last可以是0虚拟也可以是blocks中存在的长度 # 我们遍历所有可能的last值0到max_block但只处理dp[i][last] 0的状态避免无效循环 # 更高效的方式是在内部循环中我们只关心last为0或blocks中的值 # 这里为了逻辑清晰我们遍历所有last但实际很多last是0不影响效率 for last in range(max_block 1): current_ways dp[i][last] if current_ways 0: # 如果当前状态没有方案跳过 continue # 尝试铺下一块砖 for block in blocks: next_len i block if next_len n: # 不能超过总长度 continue # 检查相邻约束last block 是否为质数 # 注意当last为0起点时我们认为“第一块砖”没有相邻约束可以直接铺。 # 通常题目会说明第一块砖是否受限制。这里假设从起点开始铺任何砖都允许。 # 所以条件改为如果last0 或者 (last block)是质数 if last 0 or is_prime(last block): dp[next_len][block] (dp[next_len][block] current_ways) % MOD # 最终答案所有铺满长度n且最后一块砖为某种类型的方案数之和 ans 0 for last in range(max_block 1): ans (ans dp[n][last]) % MOD return ans # 示例使用假设题目输入 if __name__ __main__: n 10 # 道路长度 blocks [1, 2, 3] # 砖块类型 result solve_road_construction(n, blocks) print(f铺设长度为{n}的道路使用砖块{blocks}方案总数为{result})代码要点解析dp数组大小第一维是道路长度n1包含长度0。第二维是max_block1是为了能用索引直接表示last砖的长度。虽然这可能会浪费一些空间如果砖块长度不连续但代码更直观。也可以用一个字典来存储键为(i, last)。初始化dp[0][0]1这是动态规划的“种子”表示一种空方案。三重循环最外层是长度i中间层是上一块砖类型last最内层是下一块砖block。时间复杂度约为 O(n * m * max_block)在题目给定范围内通常是可接受的。转移条件if last 0 or is_prime(last block)这是本题的核心逻辑。last0表示铺设第一块砖没有前驱砖与之相邻因此无需检查质数条件。这个处理非常重要是很多同学容易忽略的边界条件。取模操作在每次加法后立即取模防止整数溢出这是竞赛编程的必备技巧。4.2 空间优化滚动数组技巧上面的基础版本使用了 O(n * max_block) 的二维数组。如果n很大比如10^5这个空间开销可能无法接受。我们注意到在状态转移时dp[i][...]只依赖于dp[i-?][...]但具体依赖于哪些i是不固定的因为砖块长度不定。然而我们可以观察到dp[i]只由那些i i的状态转移而来。虽然不能像最简单的0-1背包那样只用一维数组但我们可以发现对于last维度我们每次更新dp[next_len][block]时next_len总是大于当前的i。这意味着如果我们按i从小到大的顺序遍历在计算dp[i]时dp[i]自身作为“目标”不会被后续的i所修改因为next_len i。但是dp[i]的行会被多个不同的i更新。实际上由于砖块长度可能很小dp[i]可能由dp[i-1],dp[i-2]等很多行转移过来。标准的二维DP是必要的。但是如果题目对空间要求极其苛刻我们可以只保留last维度而用一维数组dp_last[last]来记录当前长度i下以last结尾的方案数同时用另一个数组next_dp_last来构建i1的状态这是不行的因为iblock不是固定的i1。更可行的优化是压缩last的维度我们并不需要0..max_block的所有索引我们只关心blocks中出现的长度以及0。我们可以把last的取值映射到砖块类型的索引上。这样last的维度就从max_block1缩小到了m1m种砖块虚拟起点。这是更优的做法。def solve_road_construction_optimized(n, blocks): MOD 10**9 7 m len(blocks) # 将砖块长度映射到一个连续的索引方便last维度使用。索引0留给虚拟起点。 block_to_idx {0: 0} # 虚拟砖块索引为0 for idx, blk in enumerate(blocks, start1): # 从1开始编号真实砖块 block_to_idx[blk] idx total_states m 1 # 状态数m种砖 虚拟起点 dp [[0] * total_states for _ in range(n 1)] dp[0][0] 1 # dp[0][虚拟起点] 1 # 预计算质数判断提升效率 # 假设砖块长度之和最大为 2000根据题目范围估算 MAX_SUM 2000 is_prime_table [True] * (MAX_SUM 1) is_prime_table[0] is_prime_table[1] False for i in range(2, int(MAX_SUM**0.5) 1): if is_prime_table[i]: for j in range(i*i, MAX_SUM1, i): is_prime_table[j] False for i in range(n 1): for last_idx in range(total_states): current_ways dp[i][last_idx] if current_ways 0: continue # 获取last_idx对应的砖块长度。last_idx0对应虚拟长度0。 last_len 0 if last_idx 0 else blocks[last_idx - 1] for block in blocks: next_len i block if next_len n: continue # 判断条件 if last_idx 0 or is_prime_table[last_len block]: next_last_idx block_to_idx[block] # 下一块砖的类型索引 dp[next_len][next_last_idx] (dp[next_len][next_last_idx] current_ways) % MOD ans 0 for last_idx in range(1, total_states): # 只累加真实砖块结尾的方案虚拟起点不算 ans (ans dp[n][last_idx]) % MOD return ans这个优化版本将last维度从max_block1减少到了m1空间效率更高。同时通过预计算质数表is_prime_table将每次转移时的质数判断从 O(sqrt(n)) 降到了 O(1)这是一个非常实用的时间优化技巧。5. 调试技巧与常见问题排查即便思路正确实现时也难免遇到问题。下面是我在解决这类DP问题时总结的排查清单。5.1 结果总是0或太小检查初始化这是最常见的问题。确认dp[0][0]是否设置为1。如果初始化错误整个DP表格可能全是0。检查转移条件特别是边界条件。对于第一块砖last0或last为虚拟状态你的转移条件是否允许铺设任何砖块在本例中我们使用了if last_idx 0 or is_prime_table[last_len block]。如果错误地写成了if is_prime_table[last_len block]那么第一块砖永远无法铺下导致所有dp[i][j]为0。检查数组越界确保dp[iblock]中的iblock没有超过n。在循环中务必加上if iblock n的判断。检查砖块列表确认输入的blocks列表是否正确是否包含了所有可用的砖块类型。5.2 结果比预期大很多或溢出即使取模检查取模操作确保在每次加法运算dp[next_len][next_last_idx] current_ways之后都立即取模。如果只在最后取模中间结果可能已经溢出在Python中是大整数但效率低在C/Java中会导致整数溢出。检查状态转移是否重复计数确保你的状态定义没有歧义导致同一种铺设方案通过不同路径被多次计算。在本问题中我们的状态(i, last)是唯一的转移路径也是确定的所以不会重复。但如果状态设计有重叠就可能重复计数。5.3 程序运行超时分析时间复杂度我们的算法有三层循环i(0~n)last_idx(0~m)block(m)。时间复杂度为 O(n * m²)。如果n和m都很大例如 n10000, m100那么 10000 * 100 * 100 10^8 次操作在Python中可能处于超时的边缘。优化策略预计算质数表如前所述将质数判断从 O(sqrt(S)) 降至 O(1)。减少无效循环在for last_idx循环内部如果current_ways 0直接continue跳过内层循环。我们已经做了。尝试优化内层循环对于每个last_len我们都需要遍历所有block检查质数条件。如果m很大可以预先为每个可能的last_len计算出所有能满足质数和的block列表。这样内层循环就只遍历有效的block而不是全部m个。这在m很大时效果显著。考虑更优的算法如果n很大但砖块长度种类m很小且长度值很小上述DP是可行的。如果n极大如10^9则需要用矩阵快速幂来优化线性递推但这道题通常不会到这个规模。5.4 记忆化搜索作为替代方案对于思维更偏向递归的同学也可以用记忆化搜索Memoization来实现代码可能更直观。from functools import lru_cache def solve_with_memo(n, blocks): MOD 10**9 7 blocks_tuple tuple(sorted(blocks)) # 转为元组便于哈希作为缓存键 # 预计算质数表 MAX_SUM 2000 is_prime [True] * (MAX_SUM 1) is_prime[0] is_prime[1] False for i in range(2, int(MAX_SUM**0.5)1): if is_prime[i]: for j in range(i*i, MAX_SUM1, i): is_prime[j] False lru_cache(maxsizeNone) def dfs(current_len, last_len): 返回从当前长度current_len开始铺且前一块砖长度为last_len铺到终点n的总方案数 if current_len n: return 1 # 找到一种完整方案 if current_len n: return 0 # 当前方案超长了无效 total 0 for block in blocks_tuple: next_len current_len block if next_len n: continue # 判断相邻条件 if last_len 0 or is_prime[last_len block]: total (total dfs(next_len, block)) % MOD return total % MOD # 起始状态当前长度0前一块砖长度为0虚拟 return dfs(0, 0)记忆化搜索的优点是逻辑清晰更符合人的自然思维尝试每种砖递归铺下去。但它有递归深度的限制如果n很大比如10000递归深度可能超过Python默认限制。此外它的状态(current_len, last_len)和迭代DP的状态dp[i][last]本质是一样的只是计算顺序不同。在竞赛中迭代DP通常更快且更节省栈空间。6. 举一反三线性DP的常见变体与识别“修路”问题是一个典型的带约束的线性DP。掌握它之后我们可以识别出一大类相似的问题。这类问题的共性在于有一个线性进程如道路长度、时间步长、字符串位置我们需要做出一系列决策如选择砖块、选择操作每个决策会影响当前状态并且后续决策只依赖于当前状态无后效性。其他类似场景举例爬楼梯问题LeetCode 70每次可以爬1或2阶求到楼顶的方案数。这是最简单的线性DPdp[i] dp[i-1] dp[i-2]。可以看作是砖块长度为[1,2]没有相邻约束的“修路”问题。使用硬币凑金额LeetCode 518给定不同面额硬币砖块和总金额道路长度求凑成总金额的组合数。这里没有“相邻约束”但硬币可以无限取用完全背包。状态定义为dp[i]表示凑成金额i的方案数转移为dp[i] dp[i-coin]。粉刷房子LeetCode 256有n个房子排成一列线性进程每个房子可以涂成红、蓝、绿中的一种相邻房子不能同色。求最小花费。状态可以定义为dp[i][color]表示涂完前i个房子且第i个房子涂成color色的最小花费。转移时dp[i][red] cost[i][red] min(dp[i-1][blue], dp[i-1][green])。这其实就是“修路”问题中“砖块”颜色的选择受到“相邻砖块”前一个房子颜色的约束。最长递增子序列LIS给定一个数列找最长递增子序列长度。我们可以定义dp[i]为以第i个元素结尾的LIS长度。转移时我们需要遍历j i如果nums[j] nums[i]则dp[i] max(dp[i], dp[j]1)。这里“线性进程”是数组索引“决策”是是否将nums[i]接在某个nums[j]后面“约束”是nums[j] nums[i]。识别线性DP的关键点线性结构问题通常涉及序列、时间、长度等一维进展。多阶段决策在每个阶段如每个道路单位、每个时间点、每个数组位置都需要做出一个选择。无后效性未来的决策只依赖于当前的状态而不依赖于过去是如何到达这个状态的。这正是我们能够用dp[i][...]来记录子问题解的前提。最优子结构一个问题的最优解包含其子问题的最优解。对于计数类问题如本题则是问题的总方案数可以由子问题的方案数组合而来。当你遇到一个问题感觉可以“一步一步”地解决并且每一步的选择会影响后续但后续选择又只关心当前局面时就应该高度怀疑它可以用动态规划特别是线性DP来解决。这时尝试定义状态dp[i][...]其中i表示进程...表示为了满足“无后效性”而必须记录的额外信息如本题的last然后推导状态转移方程问题就迎刃而解了。