本题参考自蓝桥杯2025国赛B组
一 原题复现
现存灯塔n个，给定点亮序列m{a1,a2,a3…am}，其中a1表示第一个操作为点亮编号为a1的灯塔。
每个相邻两个灯塔无法被同时点亮。
求从给定的点亮序列中找到一个子序列，满足能够点亮的最大灯塔数。
二 题意解析
咋一看本题似乎非常复杂。仔细分析，要求从给定的点亮序列m中找子序列，按照题目情景我们翻译过来：无非是有n个灯塔，限定了能点亮的灯塔，在相邻两个灯塔无法被点亮的前提下，以此找到能够点亮的最大灯塔数。
三 思路分析/代码详解
（一）贪心算法
我们可以利用贪心算法，依次遍历n灯塔，判断其是否在点亮序列中，如果在就点亮并跳过下一个灯塔，如果不在直接跳过本次循环。
代码如下:
（二）动态规划
看到要求最大灯塔数我们自然想到了动态规划，首先建立一个数组dp[n]，表示前n个灯塔中最多能点亮的个数。如何确定状态转移方程呢？不妨举个例子：10个灯塔，其中1,2,3,5,6,9,10可以被点亮。从头开始遍历：dp[0]=0、1✅️dp[1]=1,1❌️dp[1]=0、2✅️dp[2]=dp[0]+1,2❌️dp[2]=dp[1]、3✅️dp[3]=dp[1]+1,3❌️dp[3]=dp[2]。到此便出现差异了，当3被点亮时1也被点亮的，2没有被点亮，此时dp[3]=2。而当3没有被点亮此时只有2被点亮dp[3]=1。见微知著，对于某一个灯塔无非两种情况，状态转移方程便可写：dp[i]=max(dp[i-1],dp[i-2]+1)。想到这各位思路是否就清晰了呢，对于这个例子我就不做过多演示了，各位可以继续推导后面的情况。
代码如下：
四 总结
以上便是我关于这道灯塔问题的全部想法了，在这里我罗列了动态规划和贪心算法的思路和代码。距离蓝桥杯还有不到一个月，希望我的文章能够帮到各位。
码字不易，喜欢这篇文章的可以点点赞。
