本文共 1555 字，大约阅读时间需要 5 分钟。

题目要求计算在不触动警报装置的情况下，你一夜之内能够偷窃到的最高金额。通过分析，可以使用动态规划来解决这个问题。接下来的解决方案将详细阐述这个问题的关键思路和算法设计。

关键思路

要解决这个问题，我们需要找到一种方法，能够在不引发警报的情况下，最大化偷窃金额。每间房子之间相互连通的防盗系统，如果相邻的房子同时被偷窃，将触发报警，导致游戏失败。因此，我们只能选择间隔偷窃房子，确保不会触发报警。

这个问题可以转化为经典的“最大不相邻元素之和”问题。通过动态规划，我们可以记录到每个房子为止的最大偷窃金额，从而找到最优解。

动态规划方法

定义dp[i]为到第i个房子为止的最大偷窃金额。状态转移方程如下：

• dp[i] = max(dp[i-2] + nums[i], dp[i-1])

其中：

• dp[i-2] + nums[i]：表示选择偷窃第i个房子，此时必然不能偷窃第i-1个房子，因此前一间房子是第i-2个房子。
• dp[i-1]：表示不选择偷窃第i个房子，此时的最大偷窃金额和前一个房子的最大金额相同。

通过递归地应用上述状态转移方程，可以逐步计算每个房子的最大偷窃金额，最终得到到最后一个房子的最大金额。

算法实现

接下来，我们将设计一个动态规划算法，具体步骤如下：

伪代码

class Solution(object):    def rob(self, nums):        """Calculate the maximum amount of money that can be stolen."""        if not nums:            return 0        m = len(nums)        if m == 1:            return nums[0]        dp = [0] * m        dp[0] = nums[0]        dp[1] = max(nums[0], nums[1])        for i in range(2, m):            dp[i] = max(dp[i-2] + nums[i], dp[i-1])        return dp[m-1]

校验

通过给定的示例来验证算法的正确性：

示例1：输入=[1,2,3,1]。

• dp[0]=1
• dp[1]=2
• dp[2]=max(1+3,2)=4
• dp[3]=max(3+1,4)=4

最终结果：4，与题目给出的示例一致。

示例2：输入=[2,7,9,3,1]。

• dp[0]=2
• dp[1]=7
• dp[2]=max(2+9=11,7)=11
• dp[3]=max(9+3,11)=12
• dp[4]=max(3+1,12)=12

最终结果：12，与题目给出的示例一致。

优化提示

为了优化算法性能，可以考虑空间优化。由于动态规划只需要存储前i-1项，可以将dp数组改为三个变量，分别存储i-2, i-1, i的值。这样可以将空间复杂度从O(n)降低到O(1)，非常适合处理较大的输入规模。

总结

通过动态规划方法，我们可以在O(n)时间复杂度和O(n)空间复杂度下解决这个问题。这意味着我们可以高效地处理较大的输入数组。总之，这个方法通过状态转移方程逐步计算，每次选择最优解，从而确保在不触发报警的情况下，最大化偷取金额。

转载地址：http://qpziz.baihongyu.com/