Day 47 | 198. House Robber | 213. House Robber II | 337. House Robber III

**Day47 |198. House Robber |213. House Robber II |337. House Robber III**

### **问题描述**

####198. House Robber你是一个小偷，任务是抢劫一条街上的房屋。每间房都有不同的金额，你不能同时抢劫相邻的房屋。如果你抢了某间房的钱，那么这间房右边的房子就无法抢了。

给定一个非负整数列表 `nums`，返回你在不触发 警报 的情况下可以抢到的最大金额。

####213. House Robber II这个问题与上一个类似，但有一个不同之处：假设房屋排列在一条环形的街区中。因此，相邻房子的定义是左边和右边都不能同时抢劫。

####337. House Robber III这个问题与前两个类似，但有一个不同之处：假设房屋排列在一条线性的街区中，但是有一间特殊的房子，它可以被抢劫两次，而不会触发警报。

### **解决方案**

####198. House Robber我们可以使用动态规划来解决这个问题。我们定义一个数组 `dp`，其中 `dp[i]` 表示到达第 `i` 个房子时，可以抢到的最大金额。

def houseRobber(nums):
 n = len(nums)
 if n ==0:
 return0 dp = [0] * (n +1)
 # 初始化dp数组 for i in range(1, n +1):
 dp[i] = max(dp[i -1], nums[i -1] + dp[i -2])
 return dp[n]

####213. House Robber II我们可以使用动态规划来解决这个问题。我们定义两个数组 `dp1` 和 `dp2`，其中 `dp1[i]` 表示到达第 `i` 个房子时，可以抢到的最大金额（从左边开始），而 `dp2[i]` 表示到达第 `i` 个房子时，可以抢到的最大金额（从右边开始）。

def houseRobberII(nums):
 n = len(nums)
 if n ==1:
 return nums[0]
 dp1 = [0] * (n +1)
 dp2 = [0] * (n +1)
 # 初始化dp数组 for i in range(1, n):
 dp1[i] = max(dp1[i -1], nums[i -1] + dp1[i -2])
 dp2[i] = max(dp2[i -1], nums[n - i] + dp2[i -2])
 return max(dp1[-1], dp2[-1])

####337. House Robber III我们可以使用动态规划来解决这个问题。我们定义一个数组 `dp`，其中 `dp[i]` 表示到达第 `i` 个房子时，可以抢到的最大金额。

def houseRobberIII(nums):
 n = len(nums)
 if n ==0:
 return0 dp = [0] * (n +1)
 # 初始化dp数组 for i in range(1, n +1):
 dp[i] = max(dp[i -1], nums[i -1] + dp[max(i -2,0)])
 return dp[n]

### **总结**

这三个问题都是关于抢劫房屋的，唯一不同之处是房屋排列在一条线性的街区还是环形的街区。我们可以使用动态规划来解决这些问题，定义一个数组 `dp` 来表示到达第 `i` 个房子时，可以抢到的最大金额。

### **参考**

* [House Robber]( />* [House Robber II]( />* [House Robber III](