C++ 中的房屋窃贼 II

房屋抢劫犯问题 是动态规划问题中的一个经典示例，经常出现在算法挑战和编码面试中。它展示了如何在限制条件（阻止某些决策组合）下，通过做出决策来优化特定结果的问题解决方案。

在其最简单的形式中，房屋抢劫犯问题涉及一排房屋，每栋房屋都藏有一定数额的钱。抢劫犯的目标 是通过抢劫房屋来最大化总金额。然而，抢劫犯不能抢劫两栋相邻的房屋，因为安保系统是相连的；如果抢劫了两栋相邻的房屋，警报就会响起。

房屋抢劫犯 II（环形排列）

房屋抢劫犯 II 引入了一个额外的约束：房屋是环形排列的。这意味着第一栋和最后一栋房屋是相邻的，这增加了问题的复杂性。抢劫第一栋房屋会排除抢劫最后一栋房屋，反之亦然。

要解决这个问题，可以将其分解为两个更简单的子问题：

• 抢劫从第一栋房屋到倒数第二栋房屋（不包括最后一栋房屋）。
• 抢劫从第二栋房屋到最后一栋房屋（不包括第一栋房屋）。

通过使用房屋抢劫犯 I 中的线性动态规划方法解决这两个子问题，然后取两个结果中的最大值，就可以获得环形排列的最优解。

方法一：带有修改的递归方法

房屋抢劫犯问题在线性排列中的递归解决方案涉及探索所有可能的抢劫房屋的组合，并在每一步做出抢劫当前房屋或跳过的决定。对于房屋抢劫犯 II 中的环形排列，问题变得更加复杂，因为抢劫第一栋房屋会排除最后一栋房屋，反之亦然。

环形排列中的挑战

环形排列在第一栋和最后一栋房屋之间引入了依赖关系。这意味着：

如果你抢劫了第一栋房屋，你就不能抢劫最后一栋房屋。如果你抢劫了最后一栋房屋，你就不能抢劫第一栋房屋。为了处理这种情况，我们将问题分成两个子问题：

抢劫从第一栋房屋到倒数第二栋房屋（nums[0] 到 nums[n-2]）。

抢劫从第二栋房屋到最后一栋房屋（nums[1] 到 nums[n-1]）。

线性子问题的递归解决方案

我们将使用递归来解决这些子问题，在每一步考虑两个选项：

• 抢劫当前房屋并跳到两个房子之前的那个房屋。
• 跳过当前房屋并移动到下一个房屋。

程序

输出

Maximum amount that can be robbed: 3

说明

提供的解决方案使用带有修改的递归方法来处理房屋抢劫犯 II 问题中的房屋环形排列。通过将问题分解为两个线性子问题并递归地求解每个子问题，该解决方案确保了在不违反不抢劫两栋相邻房屋的约束的情况下，抢劫到了最大金额。

尽管这种递归方法很直接，并且展示了问题解决方法，但由于其指数时间复杂度，对于大型输入规模可能效率不高。在实际应用中，更倾向于使用动态规划方法来优化性能并减少冗余计算。

基本情况

辅助函数 robRecursive 处理当前索引超出有效范围的基线情况。如果起始索引大于结束索引 (start > end)，则返回 0。这意味着此子问题中没有剩余房屋可供考虑。

递推关系

递归的核心思想是为每栋房屋探索两种选择：

跳过当前房屋：移动到下一栋房屋，这意味着调用 robRecursive(nums, start + 1, end)。

抢劫当前房屋：将当前房屋的钱加到抢劫下一栋房屋后的结果中。这是通过调用 robRecursive(nums, start + 2, end) 并加上 nums[start] 来实现的。

对于每栋房屋，该函数计算这两种选择并返回最大值。这种逻辑确保了在不违反抢劫两栋相邻房屋的约束的同时，考虑了所有可能的房屋组合。

主函数逻辑

rob 函数是处理房屋环形排列的主函数。以下是分步逻辑：

单栋房屋情况：如果只有一栋房屋，该函数直接返回其值，因为没有相邻房屋需要考虑。

两栋房屋情况：如果只有两栋房屋，该函数返回两者之间的最大值，因为抢劫任何一栋房屋都是允许的，没有任何相邻问题。

对于超过两栋房屋的情况，将问题分解为两个子问题以处理环形性质：

情况 1：抢劫从第一栋房屋到倒数第二栋房屋。这排除了最后一栋房屋，避免了环形相邻问题。

情况 2：抢劫从第二栋房屋到最后一栋房屋。这排除了第一栋房屋，同样避免了环形相邻问题。

该函数使用 robRecursive 辅助函数来解决这两个子问题，然后取这两个情况结果中的最大值。这种方法确保解决方案遵守环形相邻约束，并找到可以抢劫的最大可能金额。

复杂度分析

时间复杂度

由于没有记忆化的递归的性质，递归方法的时​​间复杂度可能相当高。让我们一步一步分析：

递归函数调用

在 robRecursive 函数中，对于特定索引的每次调用，它会进行另外两次递归调用：一次是跳过当前房屋 (robRecursive(nums, start + 1, end))，另一次是抢劫当前房屋 (robRecursive(nums, start + 2, end))。

这种分支会导致指数数量的调用。具体来说，每次调用都会分成两个，导致一个二叉树的调用。

指数增长

在每栋房屋处，该函数会进行两次递归调用，在最坏情况下总共进行2n 次函数调用，其中 n 是房屋的数量。

这是因为递归调用树的深度可以高达 n（如果每次调用只跳过当前房屋），并且树的每个级别可以比前一个级别有两倍的调用。

总体时间复杂度

由于递归调用次数的指数增长，robRecursive 函数的时间复杂度为 O(2n)。

因此，由于主函数 rob 调用此递归函数两次（每个子问题一次），因此总体时间复杂度保持 O(2n)。这是因为在大 O 符号中会忽略常数因子。

空间复杂度

递归方法的空间复杂度由函数调用堆栈使用的空间和函数本身使用的任何额外空间决定。

函数调用堆栈

每次递归调用都会向调用堆栈添加一个新帧，直到达到基线情况。

调用堆栈的最大深度等于递归链的长度，在最坏情况下（如果每次调用只跳过当前房屋并继续到下一个），这个长度最多为 n，即房屋的数量。

每次调用的空间使用

每次调用使用的空间是恒定的（忽略递归调用本身），主要用于存储参数和返回地址。

因此，每次调用的空间复杂度为 O(1)。

总体空间复杂度

在最坏情况下，调用堆栈所需的空间最多为O(n)，其中 n 是房屋的数量。当每次调用只跳过当前房屋并继续到下一栋房屋时，会产生与房屋数量一样深的递归调用链。

因此，递归解决方案的总体空间复杂度为O(n)。

方法二：记忆化（自顶向下动态规划）

在房屋抢劫犯 II 问题中，房屋是环形排列的，这意味着第一栋和最后一栋房屋是相邻的。目标是确定可以抢劫的最大金额，而不触发警报，即不抢劫两栋相邻的房屋。

为了处理环形排列，我们将问题分解为两个线性子问题：

• 抢劫从第一栋房屋到倒数第二栋房屋。
• 抢劫从第二栋房屋到最后一栋房屋。

这确保了我们在同一个子问题中永远不会同时考虑第一栋和最后一栋房屋，从而避免了相邻问题。

程序

输出

Maximum amount that can be robbed: 3

说明

带有记忆化的递归函数 (robMemo)

此函数执行实际的递归计算，以确定在指定房屋范围内可以抢劫的最大金额。

基线情况：如果起始索引大于结束索引，这意味着没有剩余房屋可供考虑，因此函数返回 0。

记忆化检查：在执行任何计算之前，该函数会检查当前起始索引的结果是否已在 memo 数组中计算并存储。如果已存储，则函数返回此存储结果以避免冗余计算。

递归计算：如果结果不在 memo 数组中，该函数将计算最大金额，该金额可以通过以下两种方式抢劫：

跳过当前房屋并考虑下一栋房屋 (start + 1)。

抢劫当前房屋并考虑下一栋房屋之后的房屋 (start + 2)。

然后，该函数将这两种值中的最大值存储在 memo 数组中并返回它。

主函数 (rob)

单栋房屋情况：如果只有一栋房屋，该函数直接返回其值，因为没有相邻房屋需要考虑。

两栋房屋情况：如果只有两栋房屋，该函数返回两者之间的最大值，因为抢劫任何一栋房屋都是允许的，没有任何相邻问题。

复杂度分析

时间复杂度

记忆化方法的时​​间复杂度主要由递归函数 robMemo驱动，该函数使用动态规划计算从房屋范围抢劫的最大金额。

递归调用

robMemo 函数会递归地为指定范围内的每栋房屋调用一次。

对于每栋房屋，该函数会进行两次调用：一次是下一栋房屋，一次是下一栋之后的房屋。但是，由于记忆化，每栋房屋的结果只计算一次并存储在memo 数组中。

记忆化

一旦某个起始索引的结果被计算出来，它就会被存储在 memo 数组中。后续对同一起始索引的调用将以恒定的时间返回存储的结果。

这会将计算次数减少到对房屋进行线性遍历。

两个子问题

问题被分解为两个子问题：抢劫从第一栋房屋到倒数第二栋房屋，以及抢劫从第二栋房屋到最后一栋房屋。

由于记忆化，每个子问题都涉及线性数量的计算。

考虑到以上几点，解决每个子问题的时间复杂度为 O(n)，其中 n 是房屋的数量。由于我们解决了两个子问题，因此总体时间复杂度保持：O(n)。

空间复杂度

空间复杂度由用于记忆化和递归调用堆栈的存储决定。

记忆化数组

对于每个子问题，一个大小为 n 的记忆化数组存储中间结果。此数组确保每栋房屋的结果只计算一次。

我们需要两个记忆化数组（每个子问题一个）。

递归调用堆栈

在最坏情况下，递归深度可以达到 n。但是，由于我们使用了记忆化，递归的每个级别都会重用存储的结果，从而最小化递归调用的数量。

合并空间使用

每个记忆化数组贡献O(n) 空间。递归调用堆栈也贡献 O(n) 空间。由于记忆化数组和递归调用堆栈都与房屋数量成线性关系，因此总体空间复杂度为O(n)。

方法三：空间优化动态规划

房屋抢劫犯 II 问题的空间优化动态规划方法利用了我们只需要跟踪最后两个状态即可计算当前状态的观察。这显著地将空间复杂度从 O(n) 降低到 O(1)。

两个变量代替 DP 数组

在传统的 DP 方法中，我们维护一个 dp 数组，其中 dp[i] 表示从第一栋房屋到第 i 栋房屋可以抢劫的最大金额。

在空间优化方法中，我们使用两个变量 prev1 和 prev2 来表示最后两个已计算的状态：

prev1 对应于抢劫到上一栋房屋的最大金额（即 dp[i-1]）。

prev2 对应于抢劫到前一栋房屋之前的房屋的最大金额（即 dp[i-2]）。

程序

输出

Maximum amount that can be robbed: 3
Maximum amount that can be robbed: 4

说明

辅助函数：robLinear

robLinear 函数旨在解决房屋抢劫问题的线性版本，在一个特定的房屋范围内（从 start 到 end）。

参数

const std::vector<int>& nums：包含房屋值的数组。

int start：要考虑的房屋范围的起始索引。

int end：要考虑的房屋范围的结束索引。

基本情况

如果给定的范围内只有一栋房屋（start == end），则函数直接返回该房屋的值，因为没有其他房屋需要考虑。

变量

prev1 用于跟踪可以抢劫到上一栋房屋的最大金额。

prev2 跟踪可以抢劫到前一栋房屋之前的房屋的最大金额。

迭代计算

该函数迭代从 start 到 end 的房屋。对于每栋房屋，该函数通过考虑两种可能性来计算可以抢劫的最大金额：

不抢劫当前房屋：这意味着最大金额与 prev1 相同。

抢劫当前房屋：这意味着最大金额是当前房屋的值 (nums[i]) 加上 prev2。然后，该函数将 prev1 更新为这两种可能性中的最大值。

在更新 prev1 之前，将 prev1 的当前值存储在一个临时变量 temp 中，以便 prev2 可以更新为 prev1 的先前值。

循环完成后，prev1 包含在指定范围内可以抢劫的最大房屋数量。

主函数：rob

rob 函数使用 robLinear 辅助函数来处理房屋的环形排列。

边缘情况

如果数组中只有一栋房屋，则函数返回该房屋的值，因为没有相邻房屋需要考虑。

如果只有两栋房屋，则函数返回两者中的最大值，因为为了避免相邻问题，我们只能抢劫其中一栋。

将问题分解为两个子问题

为了处理环形排列，函数将问题分解为两个线性子问题：

情况 1：考虑抢劫从第一栋房屋到倒数第二栋房屋（nums[0] 到 nums[n-2]）。这避免了包含最后一栋房屋。

情况 2：考虑抢劫从第二栋房屋到最后一栋房屋（nums[1] 到 nums[n-1]）。这避免了包含第一栋房屋。

使用 robLinear 解决子问题

对于情况 1，函数调用 robLinear，范围从 0 到 n-2。

对于情况 2，函数调用 robLinear，范围从 1 到 n-1。

返回最终结果

函数返回两个子问题（case1 和 case2）结果之间的最大值，确保尊重不抢劫第一栋和最后一栋房屋的约束。

复杂度分析

时间复杂度

robLinear 函数的时​​间复杂度为 O(n)，因为它准确地处理了指定范围内每栋房屋一次。

由于 rob 函数调用 robLinear 两次（每个子问题一次），因此总体时​​间复杂度保持 O(n)。

空间复杂度

robLinear 函数的空间复杂度为O(1)，因为它只使用了恒定的额外空间（prev1、prev2 和 temp）。

rob 函数的总体空间复杂度也为 O(1)，因为辅助函数不需要额外的空间与输入规模成比例。