线性动态规划：打家劫舍问题变种——不能同时偷窃相邻房屋，但可以偷窃环形街道上的房屋（进阶版：带冷却时间和偷窃价值差异）

字数 4245 2025-12-10 09:16:39

线性动态规划：打家劫舍问题变种——不能同时偷窃相邻房屋，但可以偷窃环形街道上的房屋（进阶版：带冷却时间和偷窃价值差异）

好的，这是一个经典的线性动态规划问题“打家劫舍”（House Robber）的一个有趣变种。我们先把问题描述清楚，然后循序渐进地解决它。

问题描述

假设你是一名小偷，计划在一条环形街道上偷窃。这条街道上的房屋排成一个圈，这意味着第一间房屋和最后一间房屋是相邻的。每个房屋里都有一定数量的现金，存放在一个名为 nums 的数组中，其中 nums[i] 代表第 i 间房屋内的金额。

但这次行动有更复杂的限制：

相邻限制：你不能同时偷窃两间相邻的房屋（在环形街道上，这意味着第一间和最后一间也被视为相邻）。
冷却限制：如果你偷窃了某一间房屋，那么接下来的一间房屋（即偷窃房屋的下一间）将进入“警戒状态”，你不能偷窃它。
价值差异：没有其他额外差异，每间房屋的价值就是 nums[i]。

你的目标是：在遵守上述所有规则的前提下，偷窃到最大可能的总金额。

示例 1：
输入：nums = [2, 7, 9, 3, 1]
输出：15
解释（仅用于理解原版打家劫舍，非本题）：在原版非环形、无冷却问题中，你可以偷窃房屋 1 (金额 = 2)，房屋 3 (金额 = 9)，房屋 5 (金额 = 1)，总金额 = 2 + 9 + 1 = 12。但在本题的环形+冷却规则下，需要重新计算。

我们需要设计一个算法来计算这个最大金额。

解题思路分解

这个问题看起来复杂，但我们可以通过“化繁为简”和“状态划分”的思路来解决。

步骤 1：分解环形问题
环形街道最大的麻烦是第一间和最后一间相连。一个经典的处理技巧是：将环形问题分解成两个线性问题。

情况 A：不偷窃最后一间房屋。那么问题就变成了在数组 nums[0: n-1]（即从第0间到倒数第二间）上的线性打家劫舍问题（带冷却）。
情况 B：不偷窃第一间房屋。那么问题就变成了在数组 nums[1: n]（即从第1间到最后一间）上的线性打家劫舍问题（带冷却）。
最终的答案就是这两种情况结果的最大值。因为同时不偷第一间和最后一间的情况，已经被包含在上述至少一种情况中了。

这样，我们就把一个环形DP问题，转化为了两个线性DP问题。

步骤 2：设计线性DP状态（带冷却）
现在，我们专注于解决线性街道上的问题，但带有“偷窃后下一间不能偷”的冷却规则。
对于每一间房屋 i，我们定义三个状态，这比经典的两个状态（偷/不偷）更精细：

dp[i][0]: 表示偷窃第 i 间房屋时，能获得的最大金额。
dp[i][1]: 表示不偷窃第 i 间房屋，且第 i 间房屋不是因为上一间被偷而强制冷却时，能获得的最大金额。可以理解为“主动不偷”。
dp[i][2]: 表示不偷窃第 i 间房屋，但这是因为第 i-1 间房屋被偷了，第 i 间处于强制冷却状态时，能获得的最大金额。

为什么需要三个状态？
因为冷却规则：“偷了 i-1，就不能偷 i”。所以，当我们在位置 i 决定“不偷”时，需要知道这个“不偷”是主动选择（可以从 i-1 不偷的状态转移过来），还是被动强制（只能从 i-1 偷的状态转移过来）。这影响了 i+1 的决策。

步骤 3：推导状态转移方程
假设我们正在处理线性数组 nums。

对于 dp[i][0]（偷第 i 间）：
- 既然要偷第 i 间，那么第 i-1 间绝对不能偷。
- 第 i-1 间可以处于“主动不偷” (dp[i-1][1]) 或 “强制冷却” (dp[i-1][2]) 状态。
- 转移方程：dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + nums[i]
对于 dp[i][1]（主动不偷第 i 间）：
- 我选择不偷，并且这不是因为被 i-1 强制冷却。
- 那么第 i-1 间可以处于任何状态（偷、主动不偷、强制冷却）。因为我不偷是我自己的选择，与 i-1 无关。
- 我需要从 i-1 的所有状态中，选一个最大值过来。
- 转移方程：dp[i][1] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
对于 dp[i][2]（因冷却而不偷第 i 间）：
- 我不偷的唯一原因，就是第 i-1 间被偷了。
- 所以，前一个状态必须是 dp[i-1][0]。
- 转移方程：dp[i][2] = dp[i-1][0]

步骤 4：初始化
对于线性DP的开始（第一间房屋，i=0）：

dp[0][0] = nums[0] （偷第一间）
dp[0][1] = 0 （不偷第一间，且是主动的。因为前面没有房屋，可以视为主动不偷）
dp[0][2] = 0 （不偷第一间，且是被迫冷却。但前面没有房屋偷它，所以也是0）

步骤 5：获取线性问题的结果
对于一个长度为 m 的线性数组，偷窃完所有房屋后的最大金额，是最后一天(i = m-1)所有可能状态的最大值：
linear_result = max(dp[m-1][0], dp[m-1][1], dp[m-1][2])
因为最后一天无论是偷了、主动不偷了、还是被迫冷却了，都是合法的结束状态。

步骤 6：组合环形问题的解

如果 nums 为空，返回 0。
如果 nums 只有一个元素，只能偷这一间（注意在环形中，偷了它，相邻的“下一间”也是它自己，但因为只有一间，冷却规则不影响），所以返回 nums[0]。
否则：
- 计算 case_A = rob_linear(nums[0: n-1]) （不偷最后一间）
- 计算 case_B = rob_linear(nums[1: n]) （不偷第一间）
- 最终结果 answer = max(case_A, case_B)

举例说明

让我们用示例 nums = [2, 7, 9, 3, 1] 来验证一下思路。

情况 A：不偷最后一间，考虑 nums = [2, 7, 9, 3]

初始化：
i=0: dp[0] = [偷=2，主动不偷=0，强制冷却=0]

递推：

i=1 (nums[1]=7):
- 偷 = max(主动不偷[0]，强制冷却[0]) + 7 = max(0,0)+7 = 7
- 主动不偷 = max(偷[0]，主动不偷[0]，强制冷却[0]) = max(2,0,0)=2
- 强制冷却 = 偷[0] = 2
- dp[1] = [7, 2, 2]
i=2 (nums[2]=9):
- 偷 = max(2, 2) + 9 = 11
- 主动不偷 = max(7, 2, 2) = 7
- 强制冷却 = 7
- dp[2] = [11, 7, 7]
i=3 (nums[3]=3):
- 偷 = max(7, 7) + 3 = 10
- 主动不偷 = max(11, 7, 7) = 11
- 强制冷却 = 11
- dp[3] = [10, 11, 11]

结果：max(10, 11, 11) = 11
所以，情况A最大金额为 11。

情况 B：不偷第一间，考虑 nums = [7, 9, 3, 1]

初始化：
i=0: dp[0] = [偷=7，主动不偷=0，强制冷却=0]

递推：

i=1 (9): 偷=9, 主动不偷=7, 强制冷却=7 -> dp[1]=[9,7,7]
i=2 (3): 偷=max(7,7)+3=10, 主动不偷=max(9,7,7)=9, 强制冷却=9 -> dp[2]=[10,9,9]
i=3 (1): 偷=max(9,9)+1=10, 主动不偷=max(10,9,9)=10, 强制冷却=10 -> dp[3]=[10,10,10]

结果：max(10,10,10) = 10
所以，情况B最大金额为 10。

最终环形结果：max(11, 10) = 11。

让我们验证一下这个结果 11 是否合理。
一种可行的偷窃方案是：偷 nums[1]=7 和 nums[3]=3。

偷了房屋1(7)，那么房屋2(9)进入冷却不能偷。
然后可以偷房屋3(3)，那么房屋4(1)进入冷却不能偷。
房屋0(2)没有偷，且它不相邻于任何被偷的房屋（因为没偷房屋4，所以房屋0不算相邻于被偷房屋），但在这个方案里我们没选它。
总金额 7 + 3 = 10？等等，这只有10。

另一种方案：偷 nums[0]=2 和 nums[2]=9。

偷了房屋0(2)，房屋1(7)冷却。
然后偷房屋2(9)，房屋3(3)冷却。
房屋4(1)未被冷却（只被房屋3冷却，但房屋3没偷），但它是房屋0的邻居（环形！），而房屋0被偷了，所以房屋4也不能偷！
总金额 2 + 9 = 11。
Bingo！这个方案可行，且金额为11。它对应了我们情况A（不偷最后一间房屋 nums[4]）计算出的最优解。

算法总结与复杂度

分解环形：将原问题分解为两个线性子问题。
线性DP：对每个线性子问题，使用具有三个状态（偷、主动不偷、强制冷却）的动态规划。
状态转移：
- dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + nums[i]
- dp[i][1] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
- dp[i][2] = dp[i-1][0]
合并结果：取两个线性子问题结果的最大值。

时间复杂度：O(n)。我们需要遍历两次长度为 n-1 的数组，每次线性DP是 O(n)，所以总体是 O(n)。
空间复杂度：O(1)。在计算线性DP时，我们注意到 dp[i] 只依赖于 dp[i-1]，因此可以用三个变量滚动更新，无需存储整个DP表。

这个解法巧妙地结合了环形问题的处理技巧和带有冷却限制的精细状态设计，是动态规划中“状态机”思想的一个很好体现。

线性动态规划：打家劫舍问题变种——不能同时偷窃相邻房屋，但可以偷窃环形街道上的房屋（进阶版：带冷却时间和偷窃价值差异）好的，这是一个经典的线性动态规划问题“打家劫舍”（House Robber）的一个有趣变种。我们先把问题描述清楚，然后循序渐进地解决它。问题描述假设你是一名小偷，计划在一条环形街道上偷窃。这条街道上的房屋排成一个圈，这意味着第一间房屋和最后一间房屋是相邻的。每个房屋里都有一定数量的现金，存放在一个名为 nums 的数组中，其中 nums[i] 代表第 i 间房屋内的金额。但这次行动有更复杂的限制：相邻限制：你不能同时偷窃两间相邻的房屋（在环形街道上，这意味着第一间和最后一间也被视为相邻）。冷却限制：如果你偷窃了某一间房屋，那么接下来的一间房屋（即偷窃房屋的下一间）将进入“警戒状态”，你不能偷窃它。价值差异：没有其他额外差异，每间房屋的价值就是 nums[i] 。你的目标是：在遵守上述所有规则的前提下，偷窃到最大可能的总金额。示例 1：输入： nums = [2, 7, 9, 3, 1] 输出： 15 解释（仅用于理解原版打家劫舍，非本题）：在原版非环形、无冷却问题中，你可以偷窃房屋 1 ( 金额 = 2 )，房屋 3 ( 金额 = 9 )，房屋 5 ( 金额 = 1 )，总金额 = 2 + 9 + 1 = 12。但在本题的环形+冷却规则下，需要重新计算。我们需要设计一个算法来计算这个最大金额。解题思路分解这个问题看起来复杂，但我们可以通过“化繁为简”和“状态划分”的思路来解决。步骤 1：分解环形问题环形街道最大的麻烦是第一间和最后一间相连。一个经典的处理技巧是：将环形问题分解成两个线性问题。情况 A ：不偷窃最后一间房屋。那么问题就变成了在数组 nums[0: n-1] （即从第0间到倒数第二间）上的线性打家劫舍问题（带冷却）。情况 B ：不偷窃第一间房屋。那么问题就变成了在数组 nums[1: n] （即从第1间到最后一间）上的线性打家劫舍问题（带冷却）。最终的答案就是这两种情况结果的最大值。因为同时不偷第一间和最后一间的情况，已经被包含在上述至少一种情况中了。这样，我们就把一个环形DP 问题，转化为了两个线性DP 问题。步骤 2：设计线性DP状态（带冷却）现在，我们专注于解决线性街道上的问题，但带有“偷窃后下一间不能偷”的冷却规则。对于每一间房屋 i ，我们定义三个状态，这比经典的两个状态（偷/不偷）更精细： dp[i][0] : 表示偷窃第 i 间房屋时，能获得的最大金额。 dp[i][1] : 表示不偷窃第 i 间房屋，且第 i 间房屋不是因为上一间被偷而强制冷却时，能获得的最大金额。可以理解为“主动不偷”。 dp[i][2] : 表示不偷窃第 i 间房屋，但这是因为第 i-1 间房屋被偷了，第 i 间处于强制冷却状态时，能获得的最大金额。为什么需要三个状态？因为冷却规则：“偷了 i-1 ，就不能偷 i ”。所以，当我们在位置 i 决定“不偷”时，需要知道这个“不偷”是主动选择（可以从 i-1 不偷的状态转移过来），还是被动强制（只能从 i-1 偷的状态转移过来）。这影响了 i+1 的决策。步骤 3：推导状态转移方程假设我们正在处理线性数组 nums 。对于 dp[i][0] （偷第 i 间）：既然要偷第 i 间，那么第 i-1 间绝对不能偷。第 i-1 间可以处于“主动不偷” ( dp[i-1][1] ) 或 “强制冷却” ( dp[i-1][2] ) 状态。转移方程： dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + nums[i] 对于 dp[i][1] （主动不偷第 i 间）：我选择不偷，并且这不是因为被 i-1 强制冷却。那么第 i-1 间可以处于任何状态（偷、主动不偷、强制冷却）。因为我不偷是我自己的选择，与 i-1 无关。我需要从 i-1 的所有状态中，选一个最大值过来。转移方程： dp[i][1] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) 对于 dp[i][2] （因冷却而不偷第 i 间）：我不偷的唯一原因，就是第 i-1 间被偷了。所以，前一个状态必须是 dp[i-1][0] 。转移方程： dp[i][2] = dp[i-1][0] 步骤 4：初始化对于线性DP的开始（第一间房屋， i=0 ）： dp[0][0] = nums[0] （偷第一间） dp[0][1] = 0 （不偷第一间，且是主动的。因为前面没有房屋，可以视为主动不偷） dp[0][2] = 0 （不偷第一间，且是被迫冷却。但前面没有房屋偷它，所以也是0）步骤 5：获取线性问题的结果对于一个长度为 m 的线性数组，偷窃完所有房屋后的最大金额，是最后一天( i = m-1 )所有可能状态的最大值： linear_result = max(dp[m-1][0], dp[m-1][1], dp[m-1][2]) 因为最后一天无论是偷了、主动不偷了、还是被迫冷却了，都是合法的结束状态。步骤 6：组合环形问题的解如果 nums 为空，返回 0。如果 nums 只有一个元素，只能偷这一间（注意在环形中，偷了它，相邻的“下一间”也是它自己，但因为只有一间，冷却规则不影响），所以返回 nums[0] 。否则：计算 case_A = rob_linear(nums[0: n-1]) （不偷最后一间）计算 case_B = rob_linear(nums[1: n]) （不偷第一间）最终结果 answer = max(case_A, case_B) 举例说明让我们用示例 nums = [2, 7, 9, 3, 1] 来验证一下思路。情况 A：不偷最后一间，考虑 nums = [2, 7, 9, 3] 初始化： i=0 : dp[0] = [偷=2，主动不偷=0，强制冷却=0] 递推： i=1 (nums[ 1 ]=7): 偷 = max(主动不偷[ 0]，强制冷却[ 0]) + 7 = max(0,0)+7 = 7 主动不偷 = max(偷[ 0]，主动不偷[ 0]，强制冷却[ 0]) = max(2,0,0)= 2 强制冷却 = 偷[ 0] = 2 dp[1] = [7, 2, 2] i=2 (nums[ 2 ]=9): 偷 = max(2, 2) + 9 = 11 主动不偷 = max(7, 2, 2) = 7 强制冷却 = 7 dp[2] = [11, 7, 7] i=3 (nums[ 3 ]=3): 偷 = max(7, 7) + 3 = 10 主动不偷 = max(11, 7, 7) = 11 强制冷却 = 11 dp[3] = [10, 11, 11] 结果： max(10, 11, 11) = 11 所以，情况A最大金额为 11 。情况 B：不偷第一间，考虑 nums = [7, 9, 3, 1] 初始化： i=0 : dp[0] = [偷=7，主动不偷=0，强制冷却=0] 递推： i=1 (9): 偷=9 , 主动不偷=7 , 强制冷却=7 -> dp[1]=[9,7,7] i=2 (3): 偷=max(7,7)+3=10 , 主动不偷=max(9,7,7)=9 , 强制冷却=9 -> dp[2]=[10,9,9] i=3 (1): 偷=max(9,9)+1=10 , 主动不偷=max(10,9,9)=10 , 强制冷却=10 -> dp[3]=[10,10,10] 结果： max(10,10,10) = 10 所以，情况B最大金额为 10 。最终环形结果： max(11, 10) = 11 。让我们验证一下这个结果 11 是否合理。一种可行的偷窃方案是：偷 nums[1]=7 和 nums[3]=3 。偷了房屋1(7)，那么房屋2(9)进入冷却不能偷。然后可以偷房屋3(3)，那么房屋4(1)进入冷却不能偷。房屋0(2)没有偷，且它不相邻于任何被偷的房屋（因为没偷房屋4，所以房屋0不算相邻于被偷房屋），但在这个方案里我们没选它。总金额 7 + 3 = 10？等等，这只有10。另一种方案：偷 nums[0]=2 和 nums[2]=9 。偷了房屋0(2)，房屋1(7)冷却。然后偷房屋2(9)，房屋3(3)冷却。房屋4(1)未被冷却（只被房屋3冷却，但房屋3没偷），但它是房屋0的邻居（环形！），而房屋0被偷了，所以房屋4也不能偷！总金额 2 + 9 = 11。 Bingo！这个方案可行，且金额为11。它对应了我们情况A（不偷最后一间房屋 nums[4] ）计算出的最优解。算法总结与复杂度分解环形：将原问题分解为两个线性子问题。线性DP ：对每个线性子问题，使用具有三个状态（偷、主动不偷、强制冷却）的动态规划。状态转移： dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + nums[i] dp[i][1] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) dp[i][2] = dp[i-1][0] 合并结果：取两个线性子问题结果的最大值。时间复杂度： O(n) 。我们需要遍历两次长度为 n-1 的数组，每次线性DP是 O(n) ，所以总体是 O(n) 。空间复杂度： O(1) 。在计算线性DP时，我们注意到 dp[i] 只依赖于 dp[i-1] ，因此可以用三个变量滚动更新，无需存储整个DP表。这个解法巧妙地结合了环形问题的处理技巧和带有冷却限制的精细状态设计，是动态规划中“状态机”思想的一个很好体现。