你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：# 一次遍历两个数组的动态规划（Python3）
## 思路
这道题和我之前仓库里的[198.house-robber](https://github.com/azl397985856/leetcode/blob/master/problems/198.house-robber.md) 基本一样。 唯一的不同的小区是成环的，你不能同时偷最后一家和第一家。
注意到限制条件加上了“不能同时偷最后一家和第一家”。因此我们的思路直接是上面那道题的进一步限制。 我们考虑两种情况：
- 不偷第一家
- 不偷最后一家
而我们要找到的最大值实际上就是两个中的最大值。最直观的想法是两次遍历，每次生成一个dp，然后求解最大值即可。
## 代码
```python
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp1 = [0] * (n + 2)
dp2 = [0] * (n + 2)
# 不偷最后一个
for i in range(n - 1):
dp1[i + 2] = max(dp1[i + 1], dp1[i] + nums[i])
# 不偷第一个
for i in range(1, n):
dp2[i + 2] = max(dp2[i + 1], dp2[i] + nums[i])
return max(dp1[-2], dp2[-1])
```
实际上一次遍历足够了：
```python
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp1 = [0] * (n + 2)
dp2 = [0] * (n + 2)
for i in range(n):
if i < n - 1:
dp1[i + 2] = max(dp1[i + 1], dp1[i] + nums[i])
if i > 0:
dp2[i + 2] = max(dp2[i + 1], dp2[i] + nums[i])
return max(dp1[-2], dp2[-1])
```
更进一步，我们可以优化空间复杂度到$O(1)$:
```python
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
if n <= 2:
return max(nums)
pre1 = nums[0]
pre2 = nums[1]
cur1 = max(pre1, nums[1])
cur2 = max(pre2, nums[2])
for i in range(2, n):
if i < n - 1:
cur1, pre1 = max(pre1 + nums[i], cur1), cur1
if i > 2:
cur2, pre2 = max(pre2 + nums[i], cur2), cur2
return max(cur1, cur2)
```
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。说明:假设你总是可以到达数…
LeetCode题解142. 环形链表 II为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表。 示例 1：输入：head = [3,2,0,-4], pos = 1输出：tail connects to node index 1解释：链表中有一个环，其尾部连接到第二个节点。示例 2…
LeetCode题解113.path-sum-ii题目地址 https://leetcode.com/problems/path-sum-ii/description/ 题目描述 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. Note: A leaf…
LeetCode题解计算机为什么是基于二进制的？可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系？深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。