洛谷P12175“园艺”题解：线性DP与滚动数组优化

洛谷 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 其实也是 3+3=6，没问题）。但如果序列是 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 而不是？其实 9+9=18 是最优。想构造贪心反例很容易：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，所以可以选。那就是 9+5=14。如果不选9，可选位置1的2、位置3的2、位置5的2，得6，或者位置1的2、位置4的5得7。所以 9+5=14 确实最优。贪心在这里也能对。但动态规划才是能证明必然正确的通用方法，贪心需要额外证明，考场上一旦数据给得刁钻就凉了。所以别贪，直接 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]

按照转移方程从 i=0 逐步推：

最后 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])) # 只有 n=0 或数据缺失，理论上不会出现 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。再测一个 n=1 的边界：输入为 1 和 7 时，初始 choose = 7，not_choose = 0，不会进循环，输出 max(0, 7) = 7，结果正确。n=2 的输入 2 和 10 20，循环一次后 not_choose = max(0,10) = 10，choose = 0 + 20 = 20，输出 max(10,20) = 20，对应选更大的第二个花圃，正确。

3.4 复杂度对比：时间与空间都算清楚

做竞赛题，分析复杂度是基本功。这题的时间复杂度是 O(n)，因为每个花圃只处理一次；空间复杂度取决于写法。

• 二维数组版：O(n) 的空间，需要存 n 个二元组；
• 滚动变量版：O(1) 的空间，只保留两个状态加一个收益数组 a；
• 如果连 a 数组都不想存，甚至可以在读入后边读边推，但通常没必要，因为收益数组占用不大，而且一次全部读入代码更简单。

我把两种写法的对比整理成一张表：

蓝桥杯省赛的数据量通常不会让 O(n) 空间崩掉，但滚动变量的写法能在思维上帮你强化“状态压缩”的意识。这种压缩思路在更复杂的 DP 题里经常用到，比如背包问题的空间优化、区间 DP 的滚动数组，早掌握早受益。

4. 实战中踩过的坑与排查手册

4.1 边界特判：n=1 和空输入

这种题最容易被忽略的就是 n=1。很多新手写完循环后，在输出时直接写 dp[n-1]，结果 n=1 时 dp 数组只有一个元素，取 dp[1] 就崩了。

我自己的习惯是先把输入读进来，再做三个级别的判断：数据为空、n 为 0、n 为 1。虽然出题人大概率不会给空输入，但代码写得防御性强一点，自测的时候能省很多时间。滚动变量版本天然对 n=1 友好，因为不会进循环，直接输出 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 是 8，choose 是 13，新 not_choose 会变成 13，然后新的 choose 被算成 13 + a[i]，凭空多了一个不存在的收益，答案直接偏大；反过来如果 a[i] 是负数，答案还可能偏小。

排查方法很笨但有效：拿小数据手动跑一遍，把每个中间值打印出来，和手推表对比。我在本地调试时经常加一行 print(not_choose, choose)，确认循环里每一轮的值都对得上，再删掉重测。这种问题一旦发生，肉眼很难直接看出来，必须靠对拍或者打表。

4.3 价值为负时，初始值别乱垫底

有些题目的收益可能出现负值，比如“花圃种了反而扣分”。如果负值存在，你要先想清楚题目允不允许一个都不种。如果允许“空选”，那么最终答案可以直接是 0，初始化 not_choose = 0 就是对的，因为空选本身代表收益 0，转移时 max 会把它兜住。

但如果不允许空选，必须至少选一块花圃，那你就要小心了。n=1 且 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 导弹拦截虽然模型不同，但能帮你理解“状态表示上升/下降趋势”的套路。最后建议自己把园艺这题改成“不能连续选两个以上”，亲手实现一下，才知道加一维不是说说那么简单。

刷题不在于多，而在于每一道题你都能说出“状态是什么、为什么这么设、转移从哪来”。能说清楚这三件事，下次遇到同家族的新题，你就不慌了。