LeetCode 第 198 题：打家劫舍
传送门：198. 打家劫舍。
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。示例 2:
输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
分析：状态：dp[i] 考虑偷取 [0,i] 区间的房间号，能够偷窃到的最高金额。对于每一个房屋，我们有偷和不偷两种选择，于是得到状态转移方程：dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])。编码的时候，应注意数组下标越界问题。
Python 代码：
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 0:
return 0
if l == 1:
return nums[0]
if l == 2:
return max(nums[0], nums[1])
dp = [0 for _ in range(l)]
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, l):
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
return dp[l - 1]
下面是一种节省空间复杂度的做法：
Python 代码：
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
if n <= 2:
return max(nums)
dp = [-1] * 2
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i & 1] = max(nums[i] + dp[(i - 2) & 1], dp[(i - 1) & 1])
return dp[(n - 1) & 1]
再者，还可以使用“滚动数组”的写法：
Python 代码：“滚动数组”
class Solution:
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
if n <= 2:
return max(nums)
pre = nums[0]
cur = max(pre, nums[1])
for i in range(2, len(nums)):
temp = cur
cur = max(pre + nums[i], cur)
pre = temp
return cur
LeetCode 第 213 题：打家劫舍 II
传送门：打家劫舍 II。
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。示例 2:
输入: [1,2,3,1] 输出: 4 解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。
Python 代码：节约空间复杂度的写法
class Solution:
def __rob_helper(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
if n <= 2:
return max(nums)
dp = [-1] * 2
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i % 2] = max(nums[i] + dp[(i - 2) % 2], dp[(i - 1) % 2])
return dp[(n - 1) % 2]
def rob(self, nums):
"""
# 转换成原问题去考虑
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 0:
return 0
if l <= 3:
return max(nums)
# 抢第一家到倒数第二家得到的金钱最大值
res1 = self.__rob_helper(nums[:-1])
# 抢第二家到最后一家得到的金钱最大值
res2 = self.__rob_helper(nums[1:])
return max(res1, res2)
Java 代码：
image-20190111141406738
LeetCode 第 337 题：打家劫舍 III
传送门：337. 打家劫舍 III。
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.示例 2:
输入: [3,4,5,1,3,null,1] 3 / \ 4 5 / \ \ 1 3 1 输出: 9 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
说明：二叉树的问题，通常都用于考察递归。
分析：对于一个结点来说，分类讨论：1、偷这个结点；2、不偷这个结点。本质上与这个系列的第 1 个问题（即 第 198 题）是一样的。
注意这个结构：
if (root.left != null) {
val += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
val += rob(root.right.left) + rob(root.right.right);
}
Java 代码：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
public int rob(TreeNode root) {
// 既然是递归求解，一定是先写递归终止条件
if (root == null) {
return 0;
}
int val = root.val;
if (root.left != null) {
val += rob(root.left.left) + rob(root.left.right);
}
if (root.right != null) {
val += rob(root.right.left) + rob(root.right.right);
}
return Math.max(val, rob(root.left) + rob(root.right));
}
}
（本节完）
网友评论