leetcode——213. 打家劫舍 II

1. 引言

在这个题目中，我们需要解决的是一个打家劫舍的问题，但与之前的题目不同的是，这次是在一个圆环上进行。也就是说，第一家和最后一家是相连的，偷窃了其中一家就不能偷窃相邻的房屋。我们需要找到一种方法，在不触发警报的情况下，偷窃到最多的金额。

2. 思路解析

对于这个题目，我们可以将圆环切割成两部分：第一部分是从第一家到倒数第二家，第二部分是从第二家到最后一家。我们需要比较这两部分中能够偷窃到的最多金额，然后取较大的一个。

2.1 动态规划

对于每一家，我们有两种选择：偷窃或者不偷窃。如果我们选择偷窃当前这一家，那么上一家就不能被偷窃；如果我们选择不偷窃当前这一家，那么上一家可以被偷窃或者不被偷窃。

我们可以使用动态规划来解决这个问题。对于第一部分家庭，我们使用一个数组dp1来记录每一家的金额，其中dp1[i]表示偷窃到第i家时的最大金额。对于第二部分家庭，我们使用一个数组dp2来记录每一家的金额，其中dp2[i]表示偷窃到第i家时的最大金额。

我们可以通过动态规划的方式，从第一家开始计算dp1的值，然后从第二家开始计算dp2的值。最后返回dp1[-1]和dp2[-1]中较大的一个。

2.2 代码实现

def rob(nums):

    def robRange(nums, start, end):
        first = nums[start]
        second = max(nums[start], nums[start + 1])
        for i in range(start + 2, end):
            first, second = second, max(first + nums[i], second)
        return second
    n = len(nums)
    if n == 1:
        return nums[0]
    elif n == 2:
        return max(nums[0], nums[1])
    else:
        return max(robRange(nums, 0, n - 1), robRange(nums, 1, n))

3. 算法复杂度分析

该算法的时间复杂度为O(n)，其中n为房屋的个数。我们需要遍历每一家房屋来计算最大金额。空间复杂度为O(1)，只使用了常数个变量来保存最大金额。

4. 总结

通过切割圆环成两部分，并使用动态规划的方式来解决这个问题，我们可以高效地求解出偷窃到的最大金额。这个方法的时间复杂度为O(n)，非常高效。在实际的应用中，我们可以将其作为一个模板，用于解决类似的打家劫舍问题。