C++ 中的房屋窃贼

第一个是大家熟悉的动态规划问题 “房屋盗贼”，这在编码面试中经常出现。这个问题涉及一名狡猾的窃贼，他打算偷窃街上不同编号房屋中隐藏的钱财。也就是说，如果同一晚闯入相邻的两栋房屋，房屋中的安全系统就会响起。因此，挑战在于估算窃贼在不触发警报的情况下能够窃取的最大金额。

形式上，这个问题可以描述如下：

• 假设你有一个非负整数数组，其中每个元素代表一栋特定房屋中的钱财金额。
• 你必须确定可以在房屋中窃取的最大金额，并增加一项限制：连续的间隔内不允许抢劫两栋房屋。
• 例如，让我们看下面的数组：2, 7, 9, 3, 1。
• 最好的策略是抢劫第一、第三和第五栋房屋，这将获得总计 12 英镑。

这个问题可以看作是对资源分配进行带有约束条件的优化，因为目标通常是尽可能多地获取物品并躲避警报系统，但这相当于抢劫房屋；然而，为了躲避警报系统，不得不跳过。难点在于确定一种策略，该策略能够让你在遵守问题规则的范围内，总共窃取尽可能多的钱。

方法 1：朴素方法

房屋盗贼问题的第一个解决方案尝试是使用暴力破解技术。这需要通过某种搜索形式找到所有要抢劫的房屋子集，然后对每个子集的价值求和，并选择具有最高价值且其元素互不相邻的子集。然而，这种方法虽然正确，但正如你将看到的，对于较大的数组，它会变得计算成本高昂且效率低下。

• 递归是一种可以用于实现最简单形式的暴力破解方法。其思想是考虑每栋房屋并做出一个决定：要么抢劫这栋房屋，而不去考虑下一栋；要么不考虑这栋房屋，然后继续前进。这种决策过程可以被表述为一个递归函数，该函数计算从给定房屋开始可以抢劫的最大金额。
• 递归函数通常遵循以下逻辑：如果你决定抢劫当前房屋，你必须排除紧邻的下一栋房屋，然后跳转到再下一栋房屋。尽管游戏在你死亡时结束，但游戏被设计为开放式的，所以如果你决定不抢劫当前房屋，你可以自由地查看下一栋。所使用的函数通过递归计算，无论是抢劫还是跳过每栋房屋，直到检查完所有可能性，都可以获得的最大金额。
• 但是，这种方法在时间和空间复杂度方面有一个非常糟糕的特点；也就是说，时间复杂度是 O(n)。由于函数考虑了所有可能的抢劫房屋组合，其阶数是指数级的。在给定的公式中，n 是房屋的数量。这会导致这样一种情况：对于每栋房屋，都有两个决策要做出，并且随着房屋数量的增加，函数调用的数量会爆炸式增长。

此外，有必要讨论这种方法的空间复杂度。理想情况下，由于解决方案是递归的，空间复杂度将是 O(n)，因为递归的最大深度在最坏情况下等于房屋的数量。这会导致大量的内存消耗，尤其是在输入较大时，并且进一步说明了暴力破解方法的低效性。

输出

 
Maximum money that can be robbed (Test Case 1): 12 
Maximum money that can be robbed (Test Case 2): 4 
Maximum money that can be robbed (Test Case 3): 110 
Maximum money that can be robbed (Test Case 4): 0 
Maximum money that can be robbed (Test Case 5): 41 
Maximum money that can be robbed (Test Case 6): 100    

方法 2：优化的动态规划方法

可以用来解决房屋盗贼问题的优化动态规划方法，远优于朴素方法。朴素方法虽然易于理解，但其弱点是执行时间需要指数级。 动态规划 (DP) 在最小化旅行时间方面似乎优于暴力破解方法，因为它每个子问题只解决一次，并存储其答案以用于解决主问题以及其他子问题。这个算法技术的灵魂，正如其名称所示，在于识别这些子问题并利用最优子结构来迭代地构建解决方案。

• DP 方法的第一个要求是仔细捕捉子问题。对于每栋房屋 I，我们希望预测从前 I 栋房屋中可能窃取的最大美元金额，而不会触发任何警报。为了表示这个值，让 dp[i] 表示，这将使以下计算过程中的理解更加清晰。为了计算 dp[i]，我们考虑两种可能的场景：要么我们抢劫当前房屋 I，要么我们绕过它。如果我们抢劫房屋，我们必须直接排除前一栋房屋；这意味着总金额将等于 nums[i] 加上可以窃取的最大金额（直到房屋 i-2），这由 dp[i-2] 表示。否则，如果我们完全绕过当前房屋，总金额将等于 dp[i-1]，即仅为止 (i-1) 栋房屋提供的最大总金额。因此，dp[i] 的最佳可能解决方案是两种可能最佳方案中的较大者。
• 也就是说，在描述了子问题之后，下一步总是设置基本情况。如果最多只有一栋房屋，那么可以窃取的最大总金额就是这栋房屋中的金额，因此 dp[0] = nums[0]。在形成两栋房屋的情况下，最大金额的概念可以确定为 dp[1] = max(nums[0], nums[1])。这些基本情况使我们能够逐步构建解决方案并为每栋房屋 I 计算 dp[i]，直到数组结束。

输出

 
Maximum money that can be robbed (Test Case 1): 12 
Maximum money that can be robbed (Test Case 2): 4 
Maximum money that can be robbed (Test Case 3): 110 
Maximum money that can be robbed (Test Case 4): 0 
Maximum money that can be robbed (Test Case 5): 41 
Maximum money that can be robbed (Test Case 6): 100 
Maximum money that can be robbed (Test Case 7): 4 
Maximum money that can be robbed (Test Case 8): 30 
Maximum money that can be robbed (Test Case 9): 90 
Maximum money that can be robbed (Test Case 10): 200    

结论

总而言之，房屋盗贼问题 是一种动态规划的优化形式，它在于使用递归解决方案的正确优化。首先，可以通过使用明显的递归函数方法来解决这个问题，该方法看起来相当冗长，而且与其说是查找解决方案的有效方法，不如说具有指数级的时间复杂度。这种方法不能保证处理更大的输入，因此，我们必须寻找一种更有效的算法来解决这个问题。

动态规划为该问题提供了一种更有效的解决方案，因为它通过较小的重叠子问题来构建解决方案并存储它们的答案。因此，通过识别子问题和应用最优子结构，时间复杂度被定义为 O(n)，空间复杂度也可以优化为 O(1)。这种优化是通过使用几个变量来存储必要的子问题结果，而不是使用数组来实现的。

通过这种方式，我们可以观察到如何将一个看似计算成本如此高昂的问题转化为一个运行流畅的算法。房屋盗贼问题的动态规划解决方案不仅提供了处理大量输入的计算方法，还很好地说明了理论如何应用于实践。从朴素解决方案到优化解决方案的转变是另一个清楚表明动态规划作为算法设计阶段组织工作的一种方法的观点。