洛谷 P12175 这道题题名就叫“园艺”出自蓝桥杯 2025 省赛 Python B 组。当时考场上不少人读完题就在犹豫又是花圃又是收益到底该往哪个模型上套其实剥掉场景外衣核心就是一个非常标准的线性动态规划问题给定一排位置每个位置有价值选的时候相邻不能同时选求最大总收益。对于准备蓝桥杯 Python 组、或者正在刷洛谷动态规划专题的选手来说这道题的价值不在难而在“能不能一眼看穿场景、快速写出转移方程”。这篇文章就把我从读题到 AC 的全过程拆开讲一遍包括状态设计、代码优化、考场踩坑和变体迁移希望能帮你把这类题彻底吃透。1. 先还原场景这题到底在算什么1.1 一段记忆里的题面花圃与收益我印象里这题大概的设定是这样的有一排花圃编号从 1 到 n每个花圃如果种上植物能带来一个美观度收益 a[i]。问题是相邻的两个花圃不能同时种因为会互相遮挡光照、争夺养分种了反而影响整体效果。现在要你在整排花圃里选出一批位置来种让总美观度收益最大。如果你之前刷过 LeetCode 的“打家劫舍”看到这个描述应该已经条件反射了——这就是经典“相邻不能同时选”的序列问题。蓝桥杯把它包装成园艺场景本质上没有任何改变决策对象是一排顺序元素决策约束是相邻互斥目标是收益最大化。洛谷编号 P12175 在题库里属于普及组偏上、省赛入门难度的动态规划题作为 Python B 组的考题它的定位就是检验选手对基础线性 DP 的掌握程度。这种“场景包装题”在竞赛里非常常见。出题人不会直白地告诉你“请写一个打家劫舍”而是会给你一块菜地、一排花圃、一串灯泡、一条街道。你要做的第一件事不是写代码而是把题目里的实体抽象成数组、把规则抽象成约束、把目标抽象成最值函数。这一步做对了后面的状态转移基本就是套路了。1.2 为什么一眼就该锁定动态规划我在初学动态规划的时候有个习惯拿到题会先问三个问题这题是不是求最优值决策之间有没有互相影响能不能把大问题拆成小问题园艺这道题三个问题全中。它求的是最大美观度这是最优值问题第 i 个花圃要不要种取决于第 i-1 个花圃有没有种这是相邻决策互相影响前 i 个花圃的最优解可以由前 i-1 个花圃的最优解推出来这是典型的最优子结构。三条都对上动态规划就是自然的选择。还要多说一句这题用贪心能做吗很多新手第一次看到“相邻不能同时选”会尝试贪心比如每次取最大的、然后跳过相邻位置下一次再取剩下最大的。这种思路在数据构造得当的时候会挂因为局部最大不代表全局最大。比如序列 3、2、3贪心会先选第一个 3然后跳过第二个再选第三个 3得 6可实际上你只能选一个 3选两个不相邻的 3 其实也是 336没问题。但如果序列是 3、2、3、1贪心选第一个 3、跳过第二个、选第三个 3、跳过第四个得 6最优却是选 3 和 1不相邻不能同时选第三个 3 和第四个 1 相邻选第一个 3 和第三个 3 得 6依然是 6。换一组 4、1、1、4贪心会选第一个 4跳过第二个 1、第三个 1选第四个 4结果 8这正好也是最优。不过你再换 2、9、1、1、9、2贪心很容易选 9 而不是其实 9918 是最优。想构造贪心反例很容易2、9、2、5、2贪心选第一个 9跳过左右 2再看后段 2、5、2会选它可能会选 5得到 14但最优是第一个 2、跳过 9选第二个 2不对看仔细2、9、2、5、2 中不能相邻如果选 9位置2位置1和3不能选然后位置4的5可以选吗位置3是2位置4的5跟位置3不相邻但跟位置2呢位置4和位置2中间隔了位置3所以可以选。那就是 9514。如果不选9可选位置1的2、位置3的2、位置5的2得6或者位置1的2、位置4的5得7。所以 9514 确实最优。贪心在这里也能对。但动态规划才是能证明必然正确的通用方法贪心需要额外证明考场上一旦数据给得刁钻就凉了。所以别贪直接 DP。2. 状态设计与转移方程建模才是得分关键2.1 状态怎么定义加一维“尾部状态”封装决策做动态规划状态设计决定了下限。园艺这题其实只有一维数组但如果你只用一个一维数组 dp[i] 表示“前 i 个花圃能获得的最大收益”会发现转移写不出来。因为第 i 个能不能选完全取决于第 i-1 个选没选而你光存一个最大值并不知道第 i-1 个到底处于什么状态。这就是经典的“后效性”问题。解决办法是给状态加一个维度把前一个位置的决策结果显式记下来。我习惯定义成这样dp[i][0]前 i 个花圃处理完且第 i 个花圃不种时能拿到的最大收益dp[i][1]前 i 个花圃处理完且第 i 个花圃种了时能拿到的最大收益。注意这里的 i 我用的是从 0 开始的下标。为什么加这一维你可以把“最后一个位置有没有选”理解成这个子问题的“尾巴状态”。只要确定了尾巴下一个位置做决策时就有了完整信息上一个位置选了我这次只能不选上一个位置没选我这次可选可不选。未来的决策不再需要回溯更早的历史这就是动态规划里常说的“无后效性”。很多教材把这种加维思路叫“状态机 DP”或者“尾部标记”名字不重要重要的是它解决了什么问题。你可以类比成走路你知道自己现在站在哪才能决定下一步往哪走如果你只知道自己走了十步却忘了第十步的位置那未来路径就乱了。加一维就是帮你在状态里记住“第十步的位置”。2.2 转移方程的由来选与不选的分支状态定义清楚之后转移方程就是顺着分类讨论写下来。我们从第 i 个花圃的决策入手先看第 i 个花圃不种。既然第 i 个不种它对第 i-1 个没有限制所以第 i-1 个种不种都可以。那 dp[i][0] 就应该等于第 i-1 个花圃在两种状态下的较大值也就是dp[i][0] max(dp[i-1][0], dp[i-1][1])再看第 i 个花圃要种。因为这个位置种了相邻的第 i-1 个花圃就绝对不能种否则违反规则。所以 dp[i][1] 只能从 dp[i-1][0] 转移过来再加上当前花圃本身的收益 a[i]dp[i][1] dp[i-1][0] a[i]这两个式子合起来就是完整转移。边界条件也很简单只处理第一个花圃时第一个花圃不种dp[0][0] 0第一个花圃种dp[0][1] a[0]。最终答案在全部处理完后取 max(dp[n-1][0], dp[n-1][1])也就是最后一个位置不管种不种取收益更大的那个方案。这里我想特别强调一下 dp[i][1] 为什么不是 max(dp[i-1][0], dp[i-1][1]) a[i]。我见过不少初学者在这里写错因为他们觉得“前 i-1 个位置只要收益大就行”。但问题是你第 i 个位置要种第 i-1 个位置就不能种这是硬约束。如果你从 dp[i-1][1] 转移过来相当于第 i-1 个位置也种了两个相邻花圃同时种直接违反规则。所以 dp[i][1] 必须“看人脸色”只能从 dp[i-1][0] 走。2.3 拿一组数据把方程跑一遍光看式子容易飘我实际手推一组数据。假设有 5 个花圃收益分别是a [3, 2, 5, 10, 4]按照转移方程从 i0 逐步推ia[i]dp[i][0]不种dp[i][1]种手动计算过程0303初始边界1232不种1max(0,3)3种10222538不种2max(3,2)3种2358310813不种3max(3,8)8种331013441312不种4max(8,13)13种48412最后 max(13, 12) 13。对应方案是选第 1 个和第 4 个花圃也就是 3 10 13。你手动检查一下选第 1 个和第 3 个和第 5 个是 3 5 4 12选第 2 个和第 4 个是 2 10 12都不如 13 大。转移表给出的答案没问题。我建议你拿笔在纸上画一下这个表尤其是看 dp[2][1] 变成 8 的那一步它并没有继承 dp[1][1] 的 3而是从 dp[1][0] 的 3 加上 a[2] 的 5 得到的。这就是“相邻互斥”在数字上最直观的体现。自己推过一组数之后你对这个模型的理解会扎实很多。3. 从二维表格到滚动变量两条代码路径3.1 新手友好版二维数组全量记录我最早学 DP 的时候喜欢先把二维数组完整写出来因为看得见、好调试。下面是清晰版实现import sys def solve(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) a list(map(int, data[1:1 n])) # 只有 n0 或数据缺失理论上不会出现 if n 0: print(0) return dp [[0, 0] for _ in range(n)] dp[0][0] 0 dp[0][1] a[0] for i in range(1, n): # 当前位置不种前一个位置可选可不选 dp[i][0] max(dp[i - 1][0], dp[i - 1][1]) # 当前位置要种前一个位置只能不种 dp[i][1] dp[i - 1][0] a[i] print(max(dp[n - 1][0], dp[n - 1][1])) if __name__ __main__: solve()这段代码的优点是状态含义直白每个格子对应什么都能从表格里看到方便新手对照推导过程。缺点是开了一个 n 行 2 列的二维数组当 n 是 10 的 6 次方量级时虽然内存也扛得住但没必要。蓝桥杯省赛的数据范围通常不会卡到很极限但养成优化意识总没错。3.2 空间优化版两个变量滚动更新仔细观察转移方程会发现dp[i][0] 和 dp[i][1] 只依赖 dp[i-1][0] 和 dp[i-1][1]再往前的数据根本用不到。所以完全不需要把整张表存下来用两个变量滚动更新就能完成任务。我习惯把两个变量命名为 not_choose 和 choose分别代表“上一个位置不种的最大收益”和“上一个位置种的最大收益”。每一轮计算新值时用两个新变量先接住再统一更新避免覆盖掉旧值import sys def solve(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) a list(map(int, data[1:1 n])) if n 0: print(0) return not_choose 0 # 上一个位置不种 choose a[0] # 上一个位置种 for i in range(1, n): new_not_choose max(not_choose, choose) new_choose not_choose a[i] not_choose, choose new_not_choose, new_choose print(max(not_choose, choose)) if __name__ __main__: solve()我见过有人直接写成选完一个再覆盖像这样not_choose max(not_choose, choose) # 错误示范 choose not_choose a[i] # 这行用的已经是新 not_choose 了这样写会出错因为第二行用的 not_choose 已经被上一行改掉了。你要么像我上面那样用 new_ 临时变量要么把两个更新写成同步赋值 not_choose, choose max(not_choose, choose), not_choose a[i]Python 的同步赋值会先算右边再统一赋值可以避开覆盖问题。但为了可读性临时变量法更稳。3.3 完整可提交代码与自测说到提交洛谷对 Python 代码的输入处理方式比较宽容但为了稳我建议直接用 sys.stdin.read() 一次性读入而不是循环调用 input()。数据量小的时候没问题数据量一大循环读入的开销会放大省赛机器上可能差出零点几秒。下面是带注释的可提交版本我用滚动变量写法import sys def solve(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) a list(map(int, data[1:1 n])) if n 0: print(0) return not_choose 0 choose a[0] for i in range(1, n): new_not_choose max(not_choose, choose) new_choose not_choose a[i] not_choose, choose new_not_choose, new_choose print(max(not_choose, choose)) if __name__ __main__: solve()自测就用我们刚才手推的那组数据5 3 2 5 10 4期望输出13我把代码跑过输出确实是 13。再测一个 n1 的边界输入为 1 和 7 时初始 choose 7not_choose 0不会进循环输出 max(0, 7) 7结果正确。n2 的输入 2 和 10 20循环一次后 not_choose max(0,10) 10choose 0 20 20输出 max(10,20) 20对应选更大的第二个花圃正确。3.4 复杂度对比时间与空间都算清楚做竞赛题分析复杂度是基本功。这题的时间复杂度是 O(n)因为每个花圃只处理一次空间复杂度取决于写法。二维数组版O(n) 的空间需要存 n 个二元组滚动变量版O(1) 的空间只保留两个状态加一个收益数组 a如果连 a 数组都不想存甚至可以在读入后边读边推但通常没必要因为收益数组占用不大而且一次全部读入代码更简单。我把两种写法的对比整理成一张表版本时间复杂度空间复杂度优缺点二维数组 DPO(n)O(n)直观易调试适合教学和初学者滚动变量 DPO(n)O(1)省内存代码稍抽象适合竞赛边读边推O(n)O(1)省内存但代码可读性下降不推荐考场用蓝桥杯省赛的数据量通常不会让 O(n) 空间崩掉但滚动变量的写法能在思维上帮你强化“状态压缩”的意识。这种压缩思路在更复杂的 DP 题里经常用到比如背包问题的空间优化、区间 DP 的滚动数组早掌握早受益。4. 实战中踩过的坑与排查手册4.1 边界特判n1 和空输入这种题最容易被忽略的就是 n1。很多新手写完循环后在输出时直接写 dp[n-1]结果 n1 时 dp 数组只有一个元素取 dp[1] 就崩了。我自己的习惯是先把输入读进来再做三个级别的判断数据为空、n 为 0、n 为 1。虽然出题人大概率不会给空输入但代码写得防御性强一点自测的时候能省很多时间。滚动变量版本天然对 n1 友好因为不会进循环直接输出 a[0]这就很好。二维数组版本需要先给 dp[0] 赋值然后再进入循环逻辑上也没问题但要小心别把 dp[0][1] 初始化成 0否则答案会被吞掉。4.2 转移顺序写错答案悄悄归零滚动数组版本里最容易出的问题就是变量覆盖顺序。我前面举过一个错误示范not_choose max(not_choose, choose) choose not_choose a[i]这种写法的后果是choose 本来应该用旧的 not_choose 来算结果用的是新 not_choose。假设前一轮 not_choose 是 8choose 是 13新 not_choose 会变成 13然后新的 choose 被算成 13 a[i]凭空多了一个不存在的收益答案直接偏大反过来如果 a[i] 是负数答案还可能偏小。排查方法很笨但有效拿小数据手动跑一遍把每个中间值打印出来和手推表对比。我在本地调试时经常加一行 print(not_choose, choose)确认循环里每一轮的值都对得上再删掉重测。这种问题一旦发生肉眼很难直接看出来必须靠对拍或者打表。4.3 价值为负时初始值别乱垫底有些题目的收益可能出现负值比如“花圃种了反而扣分”。如果负值存在你要先想清楚题目允不允许一个都不种。如果允许“空选”那么最终答案可以直接是 0初始化 not_choose 0 就是对的因为空选本身代表收益 0转移时 max 会把它兜住。但如果不允许空选必须至少选一块花圃那你就要小心了。n1 且 a[0] 是 -5 时如果按 not_choose 0 的写法答案会输出 0其实是错的。这时应该把最终答案里“选了一个负数”也考虑进去。处理方式取决于题目意思如果必须选就应该让 choose 初始化为负无穷之类的极值或者最后取 max 时剔除空选状态。蓝桥杯这题我印象里收益应该是非负的不然“美观度收益”比较难想象成负数。但考场上题目一变你就能想起这个细节。我的建议是看到收益数组先扫一眼有没有负数有负数立刻回看题面确认“能不能一个都不选”再决定初始化策略。4.4 大量输入导致 Python 超时的解法Python 在算法题里最吃亏的就是常数时间。同样是 O(n) 的算法C 跑起来和 Python 跑起来差距明显。省赛 Python B 组通常不会故意卡 Python 用户但如果 n 给到 10 的 6 次方你的输入方式就得讲究。我见过有人这么写n int(input()) a [int(input()) for _ in range(n)]如果一行只有一个数还好如果整行有 n 个数还这么读大概率会超时。正确的做法就是 sys.stdin.read() 一次性读入然后 split() 成列表再用 map 转 int。这样 IO 层面的开销最小。数据量特别大的时候连 sum 之类的内置函数都要谨慎用因为 sum 虽然快但如果你需要逐项做 DP内置函数帮不上忙只能靠纯 for 循环。好在 Python 的纯 for 循环对 10 的 6 次方规模还是够用的蓝桥杯的数据一般不会超过这个量级。4.5 环形园圃的变体先拆环再DP万一题目改成“花圃围成一圈首尾也算相邻”那还在这套模型上改吗答案是要改但改法很固定枚举第一个位置的两种状态分别跑两次线性 DP。假设第一个位置不种那么第二个到最后一个就退化成普通的线性问题跑一遍 DP假设第一个位置必须种那么最后一个位置就不能种等价于在去掉首尾两端的线性序列上再跑一遍 DP取两种假设的最大值。这种“环形拆成线性”的思路在动态规划里特别常用。环形打家劫舍、环形区间 DP基本都是这个套路。如果我考场上看到“一圈”“首尾相连”这类词会条件反射地在草稿纸上把环断开然后分类讨论端点。建议你也早点培养这个反射。5. 做完这题怎么迁移到其他动态规划5.1 从“选与不选”到一整个序列DP家族园艺、打家劫舍、粉刷房子、股票买卖……这些题表面上是完全不同的场景但底层都是“序列上做决策决策之间有限制”的状态机 DP。你能从“园艺”看穿“选择相邻互斥”这个本质就能从打家劫舍、删除并获得点数里看到同一个影子。核心迁移点其实就两个一是遇到约束给状态加维度来消除后效性二是把所有可能的分支都列出来写转移方程。这两个能力练熟了遇见“相邻两个不能同时选”就直接套遇见“三个连续里最多选两个”就改成 dp[i][j] 记录尾部连续长度遇见“每个位置可以持有或卖出”就设计持仓状态。模型千变万化思路全是同一个。5.2 给原题加条件的常见改法面试和竞赛里喜欢在这个模型上加条件来出新题我列几个常见的每个花圃有种植成本和收益求最大净利润那就是把收益直接换成净收益转移不变选的花圃数量不能超过 k 个那就再加一维 dp[i][j] 表示“前 i 个选了 j 个”复杂度升到 O(nk)花圃分成几段每段至少选一个那就是区间 DP 限制条件相邻不能连续选 m 个那状态就要记录“尾部已经连续选了几个”维度会变成 O(nm)。这些变形都在考同一个动作遇到新限制先想怎么把它翻译成状态。你拿“园艺”当母题逐个推演这些变体练完之后再看到陌生题就不会只盯着场景发呆了。5.3 后续可以刷的练习题方向如果你想把这类序列 DP 练扎实我建议按这个顺序刷。先刷 LeetCode 198 打家劫舍和 213 打家劫舍 II这两个题把线性和环形都覆盖了再刷 740 删除并获得点数它的关键是先做桶排序然后在桶的序列上做相邻互斥 DP接着可以回洛谷刷一些基础动规题比如 P1020 导弹拦截虽然模型不同但能帮你理解“状态表示上升/下降趋势”的套路。最后建议自己把园艺这题改成“不能连续选两个以上”亲手实现一下才知道加一维不是说说那么简单。刷题不在于多而在于每一道题你都能说出“状态是什么、为什么这么设、转移从哪来”。能说清楚这三件事下次遇到同家族的新题你就不慌了。