大盗宝藏算法全攻略，线性DP/环形变种/实战优化，搞定所有刷题场景

上周在算法刷题社群里，有个刚入门的同学吐槽：“明明把大盗宝藏的基础代码背熟了，一遇到环形变种就直接懵圈”——这其实是很多学习者的共性问题：只懂套模板,不懂算法的核心推导和变种适配逻辑。

大盗宝藏算法，也就是算法圈熟知的“打家劫舍”问题，本质属于线性动态规划（DP）的经典分支，核心是通过决策选择（抢或不抢当前宝藏）来推导最优解，每一步的决策都会影响后续的选择空间,因此状态定义和转移方程是整个算法的灵魂。

基础版线性DP：搞定核心逻辑

先从最经典的线性大盗宝藏问题入手：给定一排宝藏屋，每个屋里有固定金额的宝藏，大盗不能连续抢两个相邻的屋子,问最多能抢到多少宝藏？

我们可以用动态规划的思路拆解：

1. 状态定义：设dp[i]表示前i间屋子能抢到的最大金额。
2. 转移方程：对于第i间屋子，有两种选择：
   • 不抢第i间：最大金额等于前i-1间的最大金额，即dp[i] = dp[i-1]
   • 抢第i间：那第i-1间不能抢，最大金额等于前i-2间的最大金额加上第i间的宝藏，即dp[i] = dp[i-2] + nums[i] 最终取两者的最大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
3. 空间优化：观察转移方程会发现，我们只需要前两个状态的值（dp[i-1]和dp[i-2]），完全不需要存储整个DP数组，可以用两个变量prev_prev（代表dp[i-2]）和prev（代表dp[i-1]）来滚动更新，把空间复杂度从O(n)降到O(1),代码实现更高效。

举个实战案例：假设宝藏屋金额为[1,2,3,1],按照优化后的逻辑计算：

• 初始状态：prev_prev=0，prev=1
• 第2间屋：max(1, 0+2)=2，更新prev_prev=1，prev=2
• 第3间屋：max(2,1+3)=4，更新prev_prev=2，prev=4
• 第4间屋：max(4,2+1)=4，最终结果为4,和实际最优解一致。

热门变种突破：环形大盗宝藏的解题思路

很多刷题者卡在环形变种上：如果宝藏屋是环形排列（首尾两间相邻），大盗不能同时抢首尾,问最多能抢到多少？

这个变种的核心是打破环形约束,把问题拆成两个线性问题：

1. 不抢第一间屋：计算从第2间到最后一间屋的最大金额（线性问题）
2. 不抢最后一间屋：计算从第一间到第n-1间屋的最大金额（线性问题）
3. 最终结果取这两个线性问题的最大值,因为这样就避免了同时抢首尾的情况。

据LeetCode 2026年1-3月的用户刷题行为数据显示，大盗宝藏相关题型的总提交量突破120万次，其中环形变种的通过率仅为23%——大部分学习者没意识到环形问题可以拆解为两个线性问题，反而试图直接修改DP状态,导致逻辑混乱。

举个案例：宝藏屋金额为[2,3,2],环形排列：

• 不抢第一间：计算[3,2]的最大金额为3
• 不抢最后一间：计算[2,3]的最大金额为3
• 最终结果为3，符合要求（不能同时抢首尾的2,所以最多抢中间的3）

进阶优化：带冷却期与约束的变种解法

除了环形，还有一类高频变种：大盗抢完一间屋后，需要冷却一天才能抢下一间（即不能连续两天抢）,这时候状态定义需要更细致：

我们可以定义三个状态：

• dp[i][0]：第i天不抢，且不是因为冷却（可以抢下一天）
• dp[i][1]：第i天抢了
• dp[i][2]：第i天不抢，因为前一天抢了（冷却状态）

转移方程如下：

• dp[i][0] = max(dp[i-1][0], dp[i-1][2])：今天不抢，要么昨天也没抢且不是冷却，要么昨天是冷却状态
• dp[i][1] = dp[i-1][0] + nums[i]：今天抢，只能是昨天没抢且不是冷却状态
• dp[i][2] = dp[i-1][1]：今天冷却，只能是昨天抢了

同样可以进行空间优化，用三个变量代替二维数组，把空间复杂度降到O(1)。

FAQ：解决你最关心的问题

Q：大盗宝藏算法只能用动态规划吗？ A：基础版如果用贪心算法，在某些特殊场景下会失效，比如宝藏屋金额为[1,100,1]，贪心会抢第一个和最后一个（总金额2），但最优解是抢中间的100，所以动态规划是通用解法,贪心只适用于特定约束场景。

Q：当宝藏屋中有0金额时，算法需要调整吗？ A：不需要，因为0不影响转移方程的逻辑，max(dp[i-1], dp[i-2]+0)等价于dp[i-1],算法会自动选择更优的路径。

Q：大规模数据下，大盗宝藏算法的效率如何？ A：基础版和变种的时间复杂度都是O(n)，空间优化后是O(1)，即使面对10^6级别的数据量，也能在毫秒级完成计算,完全满足刷题和工程场景的需求。

就是由"游戏天龙人"原创的《大盗宝藏算法全攻略：线性DP/环形变种/实战优化，搞定所有刷题场景》解析，更多深度好文请持续关注本站,我们会不断带来算法与游戏机制的硬核拆解。